C++で同じ平均を持つ分割配列

配列Aが1つあるとすると、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]

理解を深めるために、次の実装を見てみましょう-

例

#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}

出力

1