题目首先要求两个集合元素个数差最小,所以尽量均分个数。
元素个数为偶数的时候,分开后,两个集合元素个数一样,差值为 0。
元素个数为奇数的时候,分开后,元素个数差值为 1。
然后要求子集合差值尽量大,那么一个集合里放小的元素,一个集合里放大的元素就行了。
n 为奇数的时候,不够均分,就在放大元素的集合里,多放一个元素。
所以:
将数组排序后,a[0] ~ a[n/2-1] 个放在一个集合里,a[n/2] ~ a[n-1 ]剩余的放在另一个集合里。
(因为除法结果是向下取整,所以整好可以这样分)
例如:
n = 5,就将数组排序,a[0] ~ a[1] 放在一个集合,a[2] ~ a[4]放在一个集合。然后分别对两个集合求和,小的和为 s1 ,大的和为 s2。 输出:1 s2 - s1。
n = 6,就将数组排序,a[0] ~ a[2] 放在一个集合,a[3] ~ a[6] 放在一个集合。然后分别对两个集合求和,小的和为 s1 ,大的和为 s2。 输出:0 s2 - s1。
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int a[N];
int sum(int a[], int l, int r)//求数组 a[l] ~ a[r] 的和
{
int res = 0;
for(int i = l; i <= r; i++)
res += a[i];
return res;
}
int main()
{
int n;
cin >> n;
for(int i = 0; i < n; i++)
{
cin >> a[i];
}
sort(a,a + n);//排序
int s1, s2;
s1 = sum(a, 0, n/2-1);//s1 的和小
s2 = sum(a, n/2, n - 1);//s2 的和大
cout << n % 2 << " " << s2 - s1;
}
hhhh,第一次觉得我想到了最佳的解法
最佳解法好像是不需要给所有元素排序 - -
最佳的是用快排的非递归写法优化到O(n)
快选,第n/2大的数也行