admin 管理员组文章数量: 887007
晴天的魔法乐园——死亡拆分II
原题链接：
Problem Description
给定一个由整数组成的集合，集合中的整数各不相同，现在要将它分为两个子集合，使得这两个子集合的并为原集合、交为空集，同时在两个子集合的元素个数n1与n2之差的绝对值|n1-n2|尽可能小的前提下，要求它们各自的元素之和S1与S2之差的绝对值|S1-S2|尽可能大。
Input
每个输入文件中一组数据。
第一行一个正整数N（1<=N<=10000000），表示集合中的整数个数。第二行是用空格隔开的N个绝对值在6666666以内的整数。
Output
用空格隔开的两个整数，即所求的|n1-n2|与|S1-S2|。
Sample Input
5
4 2 1 3 5Sample Output
1 91、分析
数据量较大，不能使用STL的sort快排，可以使用nth_element()函数，它可以将第几大的元素放到指定的位置上，同时让大于它的元素放到右边，小于的放到左边。题目的大致意思是将集合拆分成两个，使得两个集合中的元素个数之差绝对值要尽量小，即|n1 - n2|尽可能小，同时让两个集合各自元素的和S1和S2的差的绝对值即|S1 - S2|尽可能大。很容易就想到一下方法：
①找出集合的第n/2小元素，计算集合的前n/2个元素和left和全部元素和sum，然后让sum - left得右边集合的元素和，再减left得结果，即：sum- 2 * left，在打印结果的时候需要考虑到n的奇偶性。这种思想可以通过全部测试用例（见代码1），但是却是错误的。考虑下面一个例子：
5
-1 -2 -3 1 2按照上面的方法，先找出n/2小元素，即-1，然后集合被划分为：-2 -3 -1 1 2，此时前n/2元素和left = -5, sum = -3, sum - 2 * left = 7，于是输出结果为：
1 7但是仔细想想，似乎有什么问题，当左集合元素和S1 = (-1) + (-2) + (-3) = -6；右集合和S2 = 1 + 2 = 3; |n1 - n2| = 1， 但是此时元素差却更大，|-6 - 3| = 9，即应该输出如下：
1 9基本思想如下：
② 当集合元素为偶数时，直接使用右n/2个元素之和减左n/2个元素和，结果和第一个方法一样，但是当集合个数为奇数的时候，需要根据第n/2个元素正负进行讨论，如果为正，则划归与右边集合，否则为左边集合，才能保证左集合S1-右集合S2绝对值最大，即：
[-2 -3 -1][1 2]比[-2 -3][-1 1 2]更优。
不过这样考虑却不能通过测试用例。
2、代码
代码1（可通过测试用例，但是存在问题）：
#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
long long n, sum = 0, left = 0, data[10000010];
int main(){scanf("%lld", &n);for(int i = 0; i < n; i++){scanf("%lld", &data[i]);sum += data[i];}//进行划分，将第n/2大元素放在n/2+1位置上，即data[n/2] nth_element(data, data + n / 2, data + n);for(int i = 0; i < n / 2; i++){left += data[i];}//注意结果printf("%lld %lld\n", n % 2, sum - 2 * left); return 0;
}代码2（不可通过全部测试用例）：
#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
long long n, sum = 0, left = 0, data[10000010];
int main(){scanf("%lld", &n);for(int i = 0; i < n; i++){scanf("%lld", &data[i]);}//进行划分，将第n/2大元素放在n/2+1位置上，即data[n/2] nth_element(data, data + n / 2, data + n);for(int i = 0; i < n / 2; i++){sum += data[n - i - 1] - data[i];}//问题在这里if(n % 2 == 0){printf("0 %lld\n", sum);}else{printf("1 %lld\n", sum + abs(data[n / 2]));} return 0;
}参考链接：
原文链接：.html
本文标签： 晴天的魔法乐园死亡拆分II
版权声明：本文标题：晴天的魔法乐园——死亡拆分II 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1732360972h1535205.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论