PAT(Advanced Level)A1113. Integer Set Partition

题意

将一个数组的数字分为2个集合，要求2个集合的元素个数差值尽可能小，而且要让2个集合的元素总和的差值的绝对值尽可能大

思路

• 很直观的想法是排序好之后分情况讨论
  • 2个集合的元素的个数都是偶数，那么各自求一下元素和就好了
  • 2个集合的元素的个数都是奇数，那么就分别把最中间的元素放到第1个集合或者第2个集合，看哪一种情况更好

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int get_sum(vector<int>& v, int l, int r) {
    int sum = 0;
    for(int i = l; i < r; i++) {
        sum += v[i];
    }
    return sum;
}
int main() {
    int n;
    scanf("%d", &n);
    vector<int> v;
    v.resize(n);
    for(int i = 0; i < n; i++) {
        scanf("%d", &v[i]);
    }
    sort(v.begin(), v.end());
    if(n % 2 == 0) {
        int s1 = get_sum(v, 0, v.size() / 2);
        int s2 = get_sum(v, v.size() / 2, v.size());
        cout << 0 << " " << abs(s1 - s2);
    }else {
        int s1 = get_sum(v, 0, v.size() / 2);
        int s2 = get_sum(v, v.size() / 2, v.size());
        int s3 = get_sum(v, 0, v.size() / 2 + 1);
        int s4 = get_sum(v, v.size() / 2 + 1, v.size());
        if(abs(s1 - s2) < abs(s3 - s4))
            cout << 1 << " " << abs(s3 - s4);
        else
            cout << 1 << " " << abs(s1 - s2);
    }
    return 0;
}