给定一个包含 N 个正整数的集合，请你将它划分为两个集合 A1 和 A2，其中 A1 包含 n1 个元素，A2 包含 n2 个元素。集合中可以包含相同元素。用 S1 表示集合 A1 内所有元素之和，S2 表示集合 A2 内所有元素之和。请你妥善划分，使得∣n1−n2∣ 尽可能小，并在此基础上∣S1−S2∣ 尽可能大。

2≤N≤105, 保证集合中各元素以及所有元素之和小于 231。

输入格式：

第一行包含整数 N。 第二行包含 N 个正整数。

输出格式：

在一行中输出 ∣n1−n2∣ 和 ∣S1−S2∣，两数之间空格隔开。

输入样例1：

1
2
10
23 8 10 99 46 2333 46 1 666 555

输出样例1：

1
0 3611

输入样例2：

1
2
13
110 79 218 69 3721 100 29 135 2 6 13 5188 85

输出样例2：

1
1 9359

思路

将一个集合划分为S1和S2两个集合，首先使两集合元素总数的差尽可能小，在此基础上使两集合元素和的差尽可能小

两集合元素总数的差尽可能小，即尽可能趋于0。

  1. 原集合的元素总数为偶数，则可S1和S2各分配一半元素；
  2. 原集合的元素总数为奇数，为满足两集合元素和的差尽可能小，使一个集合元素比另一个集合元素数多1即可满足

利用sort给集合排序，后半边的数存入S2，前半边存入S1，即可满足两集合元素和的差尽可能小

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <algorithm>

using namespace std;

int get_sum(int i, int j, int *ve) { //计算ve数组，索引i到j的元素和
    int ret = 0;
    for(int k = i; k <= j; k++) {
        ret += ve[k];
    }
    return ret;
}

int main() {
    int n;
    scanf("%d", &n);
    int ve[n];
    for(int i = 0; i < n; i++) {
        scanf("%d", &ve[i]);
    }
    sort(ve, ve+n);
    if(n % 2 == 0) {//偶数
        printf("0 ");
        printf("%d\n", get_sum(n / 2, n - 1, ve) - get_sum(0, n / 2 - 1, ve));
    } else {
        printf("1 ");
        printf("%d\n", get_sum(n / 2, n - 1, ve) - get_sum(0, n / 2 - 1, ve));
    }
    return 0;
}