step1
首先找到输入序列排序后下标为n / 2的数,设这个数的值为m。
该步解法参照 AcWing 786. 第k个数
step2
扫描数组,统计小于k的数的个数,记为slc,以及这些数的和,记为sl。
并且统计数组所有元素的和为sum。
如果slc == n / 2
- sum - sl * 2 即为|S1 − S2|
否则slc < n / 2
- 这种情况说明数组中存在不止一个值为m的元素。注意按照题目要求划分后的两个集合元素个数差值应尽量小,因此需要将 (n / 2 - slc)个值为k的元素划分到和较小的集合。
这种情况的|S1−S2|为sum - (n / 2 - slc) * m * 2 - sl * 2
正确性证明……略
优化效果
在本题数据范围下,大概比直接排序后求和快一倍
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int n;
int findK(int l, int r, int k){
if (l >= r) return a[l];
int i = l - 1, j = r + 1;
int x = a[l + r >> 1];
while (i < j){
while (a[++ i] < x);
while (a[-- j] > x);
if (i < j) swap(a[i], a[j]);
}
if (j - l + 1 >= k) return findK(l, j, k);
else return findK(j + 1, r, k - j + l - 1);
}
int main(){
scanf("%d", &n);
int sum = 0;
for (int i = 0; i < n; i++) scanf("%d", &a[i]), sum += a[i];
int m = findK(0, n - 1, n / 2);
int sl = 0, slc = 0;
for (int i = 0; i < n; i++){
if (a[i] < m) slc ++, sl += a[i];
}
if (n % 2 == 1){
printf("1 ");
}
else {
printf("0 ");
}
if (slc == n / 2)
printf("%d", sum - sl * 2);
else
printf("%d", sum - (n / 2 - slc) * m * 2 - sl * 2);
return 0;
}