Given a set of N (>1) positive integers, you are supposed to partition them into two disjoint sets A​1​​ and A​2​​ of n​1​​ and n​2​​ numbers, respectively. Let S​1​​ and S​2​​ denote the sums of all the numbers in A​1​​ and A​2​​, respectively. You are supposed to make the partition so that ∣n​1​​−n​2​​∣ is minimized first, and then ∣S​1​​−S​2​​∣ is maximized.

Input Specification:

Each input file contains one test case. For each case, the first line gives an integer N (2≤N≤10​5​​), and then N positive integers follow in the next line, separated by spaces. It is guaranteed that all the integers and their sum are less than 2​31​​.

Output Specification:

For each case, print in a line two numbers: ∣n​1​​−n​2​​∣ and ∣S​1​​−S​2​​∣, separated by exactly one space.

Sample Input 1:

10
23 8 10 99 46 2333 46 1 666 555

Sample Output 1:

0 3611

Sample Input 2:

13
110 79 218 69 3721 100 29 135 2 6 13 5188 85

Sample Output 2:

1 9359

 

 1 #include <stdio.h>
 2 #include <algorithm>
 3 using namespace std;
 4 const int maxn=100010;
 5 int seq[maxn];
 6 int total[maxn];
 7 int main(){
 8   int n;
 9   int sum=0;
10   scanf("%d",&n);
11   for(int i=0;i<n;i++){
12     scanf("%d",&seq[i]);
13   }
14   sort(seq,seq+n);
15   for(int i=0;i<n;i++){
16     sum+=seq[i];
17     total[i]=sum;
18   }
19   printf("%d %d",n%2,total[n-1]-2*total[n/2-1]);
20 }

View Code

注意点：计算差的时候由于总和算了前面部分，要多减一次前半部分。感觉直接算和然后相减也不会超时