题解 | #数的选择#

思路

根据贪心思想，数组 的元素尽量大，而数组 的元素尽量小，并且不难想到， 的长度应始终满足 。

不妨先对数组进行排序（假设从小到大），然后 从后面开始选择， 从数组前面开始选择。然后枚举数组 长度，求和比较是否满足 即可。为了加快求和的速度，用前缀和即可。

最后时间复杂度为 ，空间复杂度为 。

参考代码

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

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

        int n = in.nextInt();
        int[] a = new int[n + 1];
        long[] pre = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            a[i] = in.nextInt();
        }

        Arrays.sort(a);
        for (int i = 1; i <= n; i++) {
            pre[i] = pre[i - 1] + a[i];
        }

        int lenA = 1;
        boolean flag = false;
        while (2 * lenA + 1 <= n) {
            long sumA = pre[n] - pre[n - lenA];
            long sumB = pre[lenA + 1];
            if (sumB < sumA) {
                flag = true;
                break;
            }
            lenA++;
        }

        System.out.println(flag ? lenA : -1);

    }
}