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$。

思路：
从小到大排序 记录前n/2的和以及n/2~n的和即可
若n为奇数则两集合相差1反之相差0

代码：

import java.util.*;

public class Main {

	public static void main(String[] args) {
	
	    int n;
	    int []a=new int [100005];
	    Scanner sc=new Scanner(System.in);
	
	    n=sc.nextInt();
	    for(int i=0;i<n;i++) {
	        a[i]=sc.nextInt();
	    }
	    Arrays.sort(a,0,n);
	
	    int sum1=0,sum2=0;
	    for(int i=0;i<n/2;i++) {
	        sum1+=a[i];
	    }
	    for(int i=n/2;i<n;i++) {
	        sum2+=a[i];
	    }
	    sum2-=sum1;
	    if(n%2==0) sum1=0;
	    else sum1=1;
	    System.out.println(sum1+" "+sum2);
	}
}