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

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个数组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

    以上是 在C ++中以相同的平均值分割数组 的全部内容， 来源链接： utcz.com/z/341143.html

    回到顶部