1113. Integer Set Partition.md

【PAT A-1113】Integer Set Partition

题意概述

给定一组 N 个正整数，您应该将它们划分为两个不相交的集合$A_1$和$A_2$。假设$A_1$和$A_2$分别有$n_1$和$n_2$个数字，和分别为$S_1$和$S_2$。如何划分这两个集合，以便保证在$\left|n_1-n_2\right|$最小化的基础上，让$\left|S_1-S_2\right|$最大化？

输入输出格式

输入第一行中先给出一个正整数 N。第二行给出 N 个正整数。

在一行中输出$|n_1-n_2|$和$\left|S_1-S_2\right|$。

算法设计

先把给定的序列进行排序，则前$\lfloor n/2 \rfloor$个元素为集合$A_1$，其余元素为集合$A_2$，输出$\left|n_1-n_2\right|$和$\left|S_1-S_2\right|$即可。

C++代码

#include <bits/stdc++.h>
using namespace std;
using gg = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    gg ni;
    cin >> ni;
    vector<gg> v(ni);
    for (gg& i : v) {
        cin >> i;
    }
    sort(v.begin(), v.end());
    cout << (ni % 2) << " "
         << abs(accumulate(v.begin(), v.begin() + ni / 2, 0) -
                accumulate(v.begin() + ni / 2, v.end(), 0));
    return 0;
}