AcWing 1603. 整数集合划分
原题链接
简单
作者:
我是真的菜呀
,
2021-01-26 12:44:35
,
所有人可见
,
阅读 296
C++ 代码
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
int main()
{
int N;
cin >> N;
vector<int> nums(N);
for (int i = 0; i < N; i++) cin >> nums[i];
// 排序,让集合A从左端取,集合B从右边取
// 这样可以保证集合A选取的元素都为整个集合中较小的,集合B选取的都为较大的
// 最终集合A和集合B的元素之和的差值尽可能的大
sort(nums.begin(), nums.end());
int l = 0, r = N - 1, n1 = 0, n2 = 0, S1 = 0, S2 = 0;
while (l < r) {
// 让集合A、B同时取元素,可以保证两个集合的元素个数的差值尽可能小
S1 += nums[l], n1++;
S2 += nums[r], n2++;
l++, r--;
}
// l == r代表N为奇数,表示中间那个元素还没有参与计算
if (l == r) {
// 如果中间的元素小于0,则将其加入到较小的集合S1中,否则S2
if (nums[l] < 0) S1 += nums[l], n1++;
else S2 += nums[l], n2++;
}
cout << abs(n1 - n2) << ' ' << abs(S1 - S2) << endl;
return 0;
}