Chia mảng với cùng mức trung bình trong C ++

Giả sử chúng ta có một mảng A, chúng ta phải chuyển mọi phần tử của A sang danh sách B hoặc danh sách C. (Những danh sách B và C này ban đầu trống.) Chúng ta phải kiểm tra xem sau khi di chuyển như vậy, giá trị trung bình có thể không. của B bằng giá trị trung bình của C và B và C đều không trống.

Vì vậy, nếu đầu vào là - [1,2,3,4,5,6,7,8,9,10], thì kết quả sẽ là true,

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của A, tổng:=0
• để khởi tạo i:=0, khi i
• tổng số:=tổng số + A [i]

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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

Đầu vào

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

Đầu ra

1