题解 | 数组分组

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> array;
    int a, sum5 = 0, sum3 = 0, sum = 0;
    for (int i = 0; i < n; i++) {
        cin >> a;
        if (a % 5 == 0) {
            sum5 += a;
        } else if (a % 3 == 0) {
            sum3 += a;
        } else {
            sum += a;
            array.push_back(a);
        }
    }

    int diff = sum3 - sum5;

    if(array.size()==0 && diff==0){
        cout << "true";
        return 0;
    }

    sum += diff;
    if (sum % 2 != 0) {
        cout << "false";
        return 0;
    }
    sum /= 2;
    vector<int> dp;
    for (auto& e1 : array) {
        if (e1 == sum) {
            cout << "true";
            return 0;
        }

        int cur_length = dp.size();
        for (int i = 0; i < cur_length; i++) {
            int cur_sum = dp[i] + e1;
            if (cur_sum == sum) {
                cout << "true";
                return 0;
            }
            auto it = find(dp.begin(), dp.end(), cur_sum);

            if (it == dp.end()) {
                dp.push_back(cur_sum);
            }

        }

        dp.push_back(e1);
    }
    cout << "false";
    return 0;
}
// 64 位输出请用 printf("%lld")

1. 算出5整除和3整除数组的差值diff
2. 算出，剩下数字的和sum
3. (sum+diff)/2就是我们要凑出来的数字，如果不是偶数直接false
4. 用dp的办法看剩下数字能不能凑出sum= (sum+diff)/2