题解
要使的|n1 - n2|
尽可能小,那么我们肯定是让两个集合元素相等或者是只差1,所以:
- n为偶数时,差为0
- n为奇数是,差为1
至于哪边多哪边少无所谓,反正差值会取绝对值。
要使|S1-S2|
尽可能大,那么我们肯定是要让S1
中的元素尽可能小,S2
中的元素尽可能大,所以我们排个序就行。
下面展示一下C++ accumulate
函数的用法,可以求指定容器区间和,下面我们求[0, n / 2)
和[n / 2, n)
的和
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int arr[N];
int main() {
int n;
cin >> n;
for(int i = 0; i < n; i++) cin >> arr[i];
sort(arr, arr + n);
int diff1 = n & 1 ? 1 : 0;
int diff2 = accumulate(arr, arr + n / 2, 0) - accumulate(arr + n / 2, arr + n, 0);
// for(int i = 0; i < n; i++) {
// if(i < n / 2) diff2 += arr[i];
// else diff2 -= arr[i];
// }
cout << diff1 << " " << abs(diff2) << endl;
return 0;
}