C++에서 동일한 평균으로 배열 분할

<시간/>

하나의 배열 A가 있다고 가정하고 A의 모든 요소를 목록 B나 목록 C로 이동해야 합니다. (이 목록 B와 C는 처음에는 비어 있습니다.) 이러한 이동 후에 평균 값이 다음과 같은지 확인해야 합니다. B의 평균값은 C의 평균값과 같고 B와 C는 모두 비어 있지 않습니다.

따라서 입력이 − [1,2,3,4,5,6,7,8,9,10]과 같으면 결과는 true가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

n :=A의 크기, 총계 :=0
초기화 i의 경우:=0, i
총계 :=총계 + A[i]

isPossible :=false, m :=n / 2

초기화 i:=1의 경우, i <=m이고 not isPossible이 0이 아닌 경우 업데이트(i를 1만큼 증가), 수행 -

total * i mod n이 0과 같으면 -
- isPossible :=사실

isPossible이 0이 아닌 경우 -

거짓 반환

크기 (total + 1) x (n / 2) + 1)의 2D 배열 dp 하나 정의

dp[0, 0] :=참

초기화 i의 경우:=0, i

x :=A[i]

j 초기화의 경우:=total, j>=x일 때 업데이트(j를 1만큼 감소), −

초기화 l의 경우:=1, l <=(n / 2)일 때 업데이트(l을 1씩 증가), 수행 -
- dp[j, l] :=dp[j, l] 또는 dp[j - x, l - 1]

i:=1 초기화의 경우, i <=(n / 2)일 때 업데이트(i를 1만큼 증가), −

(total * i) mod n이 0이고 dp[total * i / n, i]가 0이 아닌 경우 -
- 참을 반환

거짓 반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   bool splitArraySameAverage(vector<int>& A) {
      int n = A.size();
      int total = 0 ;
      for(int i = 0; i < n; i++) total += A[i];
      bool isPossible = false;
      int m = n / 2;
      for (int i = 1; i <= m && !isPossible; ++i)
      if (total*i%n == 0) isPossible = true;
      if (!isPossible) return false;
      vector < vector <bool> > dp(total + 1, vector <bool>((n / 2) + 1));
      dp[0][0] = true;
      for(int i = 0; i < n; i++){
         int x = A[i];
         for(int j = total; j >= x; j--){
            for(int l = 1; l <= (n / 2); l++){
               dp[j][l] = dp[j][l] || dp[j - x][l - 1];
            }
         }
      }
      for(int i = 1 ; i <= (n / 2); i++){
         if((total * i) % n == 0 && dp[total * i / n][i]) return true;
      }
      return false;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,2,3,4,5,6,7,8,9,10};
   cout << (ob.splitArraySameAverage(v));
}

입력

{1,2,3,4,5,6,7,8,9,10}

C++에서 동일한 평균으로 배열 분할

예시

입력

출력