AcWing 1603. 整数集合划分

题目

给定一个包含 $N$ 个正整数的集合，请你将它划分为两个集合 $A_1$ 和 $A_2$，其中 $A_1$ 包含 $n_1$ 个元素，$A_2$ 包含 $n_2$ 个元素。

集合中可以包含相同元素。

用 $S_1$ 表示集合 $A_1$ 内所有元素之和，$S_2$ 表示集合 $A_2$ 内所有元素之和。

请你妥善划分，使得 $|n_1−n_2|$ 尽可能小，并在此基础上 $|S_1−S_2|$ 尽可能大。

输入格式
第一行包含整数 $N$。

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

输出格式
在一行中输出 $|n_1−n_2|$ 和 $|S_1−S_2|$，两数之间空格隔开。

数据范围
$2≤N≤10^5$,
保证集合中各元素以及所有元素之和小于 $2^{31}$。

输入样例1：

10
23 8 10 99 46 2333 46 1 666 555

输出样例1：

0 3611

输入样例2：

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

输出样例2：

1 9359

思路

题目首先要求两个集合元素个数差最小，所以尽量均分个数。

元素个数为偶数的时候，分开后，两个集合元素个数一样，差值为 0。

元素个数为奇数的时候，分开后，元素个数差值为 1。

然后要求子集合差值尽量大，那么一个集合里放小的元素，一个集合里放大的元素就行了。

n 为奇数的时候，不够均分，就在放大元素的集合里，多放一个元素。

题解 - yxc版本

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
int w[N];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &w[i]);
    sort(w, w + n);

    int s1 = 0, s2 = 0;
    for (int i = 0; i < n / 2; i ++ ) s1 += w[i];
    for (int i = n / 2; i < n; i ++ ) s2 += w[i];

    printf("%d %d\n", n % 2, s2 - s1);

    return 0;
}