题目描述
给定一个包含 N 个正整数的集合,请你将它们划分为两个不相交的集合 A1 和 A2,其中 A1 包含 n1 个元素,A2 包含 n2 个元素。
用 S1 表示集合 A1 内所有元素之和,S2 表示集合 A2 内所有元素之和。
请你妥善划分,使得 |n1−n2| 尽可能小,并在此基础上 |S1−S2| 尽可能大。
分析
|n1-n2|尽可能小也就是两部分包含的整数尽可能相等,所以一边一半即可,偶数个时恰好对半分,为0,奇数个时为1。
在此基础上|S1-S2|尽可能大,因此,只需排序后让S1放小的,S2放大的即可。
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N=100010;
int q[N];
int n;
int main(){
cin>>n;
for(int i=0;i<n;i++){
cin>>q[i];
}
sort(q,q+n);
int s1=0,s2=0,n1=0,n2=0;
for(int i=0;i<n/2;i++){
s1+=q[i];
n1++;
}
for(int i=n/2;i<n;i++){
s2+=q[i];
n2++;
}
cout<<abs(n1-n2)<<' '<<abs(s1-s2);
return 0;
}