AcWing 1603. 整数集合划分

给定一个包含 N 个正整数的集合，请你将它们划分为两个不相交的集合 A1 和 A2，其中 A1 包含 n1 个元素，A2 包含 n2 个元素。

用 S1 表示集合 A1 内所有元素之和，S2 表示集合 A2 内所有元素之和。

请你妥善划分，使得 |n1−n2| 尽可能小，并在此基础上|S1−S2| 尽可能大。

输入格式

第一行包含整数 N。

第二行包含 N 个正整数。

输出格式

再一行中输出 |n1−n2| 和 |S1−S2|，两数之间空格隔开。

数据范围

2≤N≤10^5,
保证集合中各元素以及所有元素之和小于 2^31。

输入样例1：

10
23 8 10 99 46 2333 46 1 666 555

输出样例1：

0 3611

输入样例2：

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

输出样例2：

1 9359

思路 ：想让|S1-S2| 尽可能的大，S1取集合中的数越大越好，S2取集合中的数越小越好，sort排序nums数组中元素后，为了|n1−n2| 尽可能小，每次S1,S2各取一个nums数组元素，我们可以使用双指针遍历nums数组等效.

#include<iostream>
#include<algorithm>
#include<memory.h>
using namespace std;
int n;
int nums[100010];
int main(){
    memset(nums,0,sizeof nums);
    cin>>n;
    for(int i=0;i<n;i++) cin>>nums[i];
    sort(nums,nums+n);
    int ans=0;
    if(n%2==0) cout<<0<<' ';
    else cout<<1<<' ';
    for(int i=0,j=n-1;i<=j;i++,j--){
        ans+=(nums[j]-nums[i]);
        if(i==j) ans+=nums[i];
    }
    cout<<ans;
    return 0;
}