Split Array ด้วยค่าเฉลี่ยเท่ากันใน C ++

สมมุติว่าเรามีอาร์เรย์ A หนึ่งอัน เราต้องย้ายทุกองค์ประกอบของ A ไปที่รายการ B หรือรายการ C (รายการ B และ C เหล่านี้ว่างในตอนแรก) เราต้องตรวจสอบว่าหลังจากการย้ายดังกล่าว เป็นไปได้ว่าค่าเฉลี่ย ของ B เท่ากับค่าเฉลี่ยของ C และ B และ C ไม่เว้นว่างทั้งคู่

ดังนั้นหากอินพุตเป็น − [1,2,3,4,5,6,7,8,9,10] ผลลัพธ์จะเป็นจริง

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• n :=ขนาด A รวม :=0
• สำหรับการเริ่มต้น i :=0 เมื่อฉัน
• รวม :=รวม + 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