在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
如果总数*imodn等于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）modn等于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