AcWing 1603. 整数集合划分
原题链接
简单
作者:
回头不是从前
,
2021-01-26 13:08:48
,
所有人可见
,
阅读 317
排序后将数组分成两部分,如果有偶数个元素就等分,奇数个元素就分为n/2和n/2+1
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int d[N];
int res, n;
int main() {
cin >> n;
for(int i = 0; i < n; ++i) cin >> d[i];
sort(d, d + n); // 可用快速选择优化到O(n)
int l = 0, mid = n >> 1, r = n;
cout << (n & 1) << ' ';
int cl = 0, cr = 0;
for(int i = l; i < mid; ++i) cl += d[i];
for(int i = mid; i < r; ++i) cr += d[i];
cout << cr - cl;
return 0;
}