C++ में समान औसत के साथ ऐरे विभाजन (Split Array With Same Average)

मान लीजिए हमारे पास एक ऐरे A है, हमें A के प्रत्येक तत्व को या तो सूची B या सूची C में ले जाना है। (ये सूचियां B और C शुरू में खाली हैं।) हमें जांचना है कि क्या इस तरह के स्थानांतरण के बाद, यह संभव है कि B का औसत मूल्य C के औसत मूल्य के बराबर हो, और B और C दोनों गैर-खाली हों।

तो यदि इनपुट [1,2,3,4,5,6,7,8,9,10] जैसा है, तो परिणाम true होगा,

इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे -

• n := A का आकार, total := 0
• i := 0 से प्रारंभ करें, जब i < n, i बढ़ाते हुए, करें -
  • total := total + A[i]
• isPossible := false, m := n / 2
• i := 1 से प्रारंभ करें, जब i <= m और isPossible शून्येतर नहीं है, i बढ़ाते हुए, करें -
  • यदि total * i mod n, 0 के समान है, तो -
    • isPossible := true
• यदि isPossible शून्येतर नहीं है, तो -
  • false वापस करें
• आकार (total + 1) x (n / 2) + 1) का एक 2D ऐरे dp परिभाषित करें
• dp[0, 0] := true
• i := 0 से प्रारंभ करें, जब i < n, i बढ़ाते हुए, करें -
  • x := A[i]
  • j := total से प्रारंभ करें, जब j >= x, j घटाते हुए, करें -
    • l := 1 से प्रारंभ करें, जब l <= (n / 2), l बढ़ाते हुए, करें -
      • dp[j, l] := dp[j, l] OR dp[j - x, l - 1]
• i := 1 से प्रारंभ करें, जब i <= (n / 2), i बढ़ाते हुए, करें -
  • यदि (total * i) mod n, 0 के समान है और dp[total * i / n, i] शून्येतर है, तो -
    • true वापस करें
• false वापस करें

बेहतर समझ के लिए निम्न कार्यान्वयन देखें -

उदाहरण

#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