Chia mảng cùng trung bình (Split Array With Same Average) trong C++

Cho mảng A, chia thành 2 mảng con B và C (không rỗng) sao cho trung bình cộng của B bằng trung bình cộng của C. Trả về true/false.

Ý tưởng

Trung bình B = trung bình C = trung bình A. Cần tìm tập con kích thước k (1 ≤ k ≤ n/2) có tổng = total * k / n (phải là số nguyên). Dùng DP knapsack: dp[t][k] = có thể tạo tổng t với k phần tử không.

Chương trình C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool splitArraySameAverage(vector<int>& A) {
        int n = A.size();
        int total = accumulate(A.begin(), A.end(), 0);
        bool possible = false;
        for(int i=1; i<=n/2 && !possible; i++)
            if(total * i % n == 0) possible = true;
        if(!possible) return false;

        vector<vector<bool>> dp(total+1, vector<bool>(n/2+1, false));
        dp[0][0] = true;
        for(int x : A) {
            for(int j=total; j>=x; j--)
                for(int k=1; k<=n/2; k++)
                    dp[j][k] = dp[j][k] || dp[j-x][k-1];
        }
        for(int i=1; i<=n/2; i++)
            if((total * i) % n == 0 && dp[total * i / n][i]) return true;
        return false;
    }
};

int main() {
    Solution ob;
    vector<int> v = {1,2,3,4,5,6,7,8,9,10};
    cout << ob.splitArraySameAverage(v); // 1 (true)
    return 0;
}

Kết quả

1