[C++知识库]PTA甲级 1113 Integer Set Partition (C++)

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 $\mid n_1?n_2\mid$ is minimized first, and then $\mid S_1?S_2\mid$ is maximized.

Input Specification:

Each input file contains one test case. For each case, the first line gives an integer $N(2\le N\le 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: $\mid n_1?n_2\mid$ and $\mid S_1?S_2\mid$, 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

Solution:

// Talk is cheap, show me the code
// Created by Misdirection 2021-08-25 22:43:48
// All rights reserved.

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

using namespace std;

int main(){
    int n;
    cin >> n;

    vector<int> nums(n);
    for(int i = 0; i < n; ++i) cin >> nums[i];

    sort(nums.begin(), nums.end());

    int s1 = 0, s2 = 0;

    for(int i = 0; i < n; ++i){
        if(i < n / 2) s1 += nums[i];
        else s2 += nums[i];
    }

    printf("%d %d\n", n % 2, s2 - s1);

    return 0;
}