题目描述

题目意思是把一个集合一分为二，A，B

s1表示第一个集合的和，s2表示第二个集合的和

n1表示第一个集合的元素数量，n2表示第二个集合的元素数量

在 |n1−n2| 尽可能小的情况下，使得 |S1−S2| 尽可能大

题解

可以考虑用双指针算法

如果是偶数的话，就让A,B两个集合中的元素相等，如果是奇数的话，就把中间的那个元素给B集合

然后从小到大排序，让A集合加入小的元素，B集合加入大的元素，就达到我们的效果了

代码

import java.util.Scanner;
import java.util.Arrays;

public class Main{
    static int N = 100010;

    public static void main(String[] args){
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();

        int[] a = new int[n];
        for(int i = 0; i < n; i ++) a[i] = in.nextInt();

        Arrays.sort(a);                 //从小到大排序

        int s1 = 0,s2 = 0,n1 = 0, n2 = 0;

        for(int i = 0, j = n - 1; i <= j; i ++, j--)
        {
            s1 += a[i];
            s2 += a[j];
            n1 ++;
            n2 ++;
            if(n % 2 != 0 && i == (n - 1) / 2)    //如果n是奇数的话，就把中间数给s2
            {
                s2 = s2 + a[(n - 1) / 2];
                n2 ++;
            }
        }

        System.out.print(n2 - n1 + " ");
        System.out.print(s2 - s1);
    }
}