PAT-A 真题 – 1113 Integer Set Partition

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 \leq N \leq 1 0^{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

题目大意：给定一个序列，拆成两个含有n1个和n2个元素的序列，他们的和分别为S1和S2。要求|n1-n2|最小，|S1-S2|最大。

这是一道贪心算法类问题，代码如下：

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

int main(){
  int n;
  cin >> n;
  vector<int> num;
  for(int i = 0; i < n; i++){
    int _;
    cin >> _;
    num.push_back(_);
  }
  sort(num.begin(), num.end());
  cout << n%2 << ' ';
  int S1 = 0, S2 = 0;
  for(int i = 0; i < n; i++){
    if(i < n/2) S1 += num[i];
    else S2 += num[i];
  }
  cout << abs(S1 - S2);
  return 0;
}

斐斐のBlog