1113 Integer Set Partition (25 分)

本文主要是介绍1113 Integer Set Partition (25 分)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1113 Integer Set Partition (25 分)

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​​ −n2​​ ∣ is minimized first, and then ∣S​1​​ −S2​​ ∣ 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 ∣S1​ −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

#include<bits/stdc++.h>
using namespace std;
int main() {int n, n1 = 0, n2 = 0;scanf("%d", &n);vector<int> v(n);for (int i = 0; i < n; i++) {scanf("%d", &v[i]);}sort(v.begin(), v.end());for (int i = 0; i < n; i++) {if (i <= n / 2 - 1) n1 += v[i];else n2 += v[i];}if (n % 2 == 0) printf("0 ");else printf("1 ");printf("%d", n2 - n1);
}

这篇关于1113 Integer Set Partition (25 分)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---