|n2 - n1| 要小的前提下,|s2 - s1| 要大。
一个数组分两份,数组元素个数为奇数的时候,|n2 - n1|最小为1,数组元素个数为偶数的时候,|n2 - n1|最小为0。
排序后,求前半部分和 h1,后半部分和h2(奇数就让后半部分都一个元素),这样就能让|s2 - s1|最大。
数组元素个数为奇数的时候,输出 1 h2 - h1。
数组元素个数为偶数的时候,输出 0 h2 - h1 即可。
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
int a[N];
int n;
int main(){
cin>>n;
for(int i = 0;i < n; i++)
cin>>a[i];
sort(a,a+n);
int h1 = 0, h2 = 0;//h1 前半部分和,h2 后半部分和
int i = 0;
for(; i < n/2 ; i++)
{
h1 += a[i];
h2 += a[i + n/2];
}
if(i < n)//奇数的时候,计算h2会丢掉最后一个元素,在这里加上
h2 += a[i + n/2];
int jo = n % 2;
cout<< jo <<" "<< h2 - h1;
}
有问题直接评论即可,
求大哥手下留情
这样不就变成两个相交的集合了吗
不会的,排序后把数组分成了两半,不会有交集的
不是说可以有相同的数吗?不能有交集吗?
但也是,有交集,相减的时候相同的数抵消了。所以还是不要有交集的好。