在C ++中以相同的平均值分割数组

假设我们有一个数组A，我们必须将A的每个元素移到列表B或列表C。（这些列表B和C最初是空的。）我们必须检查这样的移动之后，平均值是否可能B的C等于C的平均值，并且B和C均为非空。

因此，如果输入类似于− [[1,2,3,4,5,6,7,8,9,10]，那么结果将为true，

为了解决这个问题，我们将遵循以下步骤-

• n：= A的大小，总计：= 0

• 对于初始化i：= 0，当i <n时，更新（将i增加1），执行-

• 总计：=总计+ A [i]

• isPossible：=假，m：= n / 2

• 对于初始化i：= 1，当i <= m而不是isPossible非零时，更新（将i增加1），-

• isPossible：= true

• 如果总数* i mod n等于0，则-

• 如果不是isPossible为非零，则-

• 返回假

• 定义一个2D数组dp，大小为（总数+ 1）x（n / 2）+ 1）

• dp [0，0]：= true

• 对于初始化i：= 0，当i <n时，更新（将i增加1），执行-

• 对于初始化l：= 1，当l <=（n / 2）时，更新（将l增加1），-

• dp [j，l]：= dp [j，l]或dp [j-x，l-1]

• x：= A [i]

• 对于初始化j：= total，当j> = x时，更新（将j减1），执行-

• 对于初始化i：= 1，当i <=（n / 2）时，更新（将i增加1），-

• 返回真

• 如果（total * i）mod n等于0并且dp [total * i / n，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