AcWing 1603. 整数集合划分
原题链接
简单
作者:
ljhs
,
2021-01-26 11:38:06
,
所有人可见
,
阅读 340
题意
- 有n个数
- 分为两部分
- 要求两部分数的数量之差绝对值最小且两部分所有数的和的差最大
分析
- 如何保证数量之差最小?
将两部分划分为尽量等长,若n为偶数->两部分同长、n为奇数->两部分长度仅差1。
- 如何保证两部分和的差最大?
对n个数排序:取前n/2的数划分为一部分,后面为一部分。
AC代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
int n;
int q[N];
int main(){
cin >> n;
for(int i = 0; i < n; i++) cin >> q[i];
sort(q,q+n);
int s1 = 0,s2 = 0;
for(int i = 0; i < n; i++){
if(i < (n >> 1)) s1 += q[i];
else s2 += q[i];
}
cout << (n & 1) << ' ' << (s2 - s1) << endl;
return 0;
}