2171.拿出最少数目的魔法豆

题目链接
题目描述： 给定一个 正整数 数组 beans ，其中每个整数表示一个袋子里装的魔法豆的数目。

排序+前缀和+后缀和

请你从每个袋子中 拿出 一些豆子（也可以 不拿出），使得剩下的 非空 袋子中（即 至少还有一颗 魔法豆的袋子）魔法豆的数目 相等。一旦把魔法豆从袋子中取出，你不能再将它放到任何袋子中。

请返回你需要拿出魔法豆的 最少数目。

分析：如果最后非空袋子的魔法豆数量为x，因为袋子中无法添加豆子，所以原本比x小的，只能全部取出。
此时只有两种情况：

1. 原本魔法豆数量大于x：都变为x，假设有3个袋子数量大于x，那么就是这三个袋子魔法豆总数-3x，就是需要取出的魔法豆数量。
2. 原本魔法豆数量小于x：全部取出。假设有4个袋子数量小于x，那么就是这四个魔法袋豆总数，就是需要取出的魔法豆数量。

也就是说，需要关注的数据有两个，比x大的元素之和，比x小的元素之和。
自然想到前缀和与后缀和
先排序，做累加，即可得到前缀和与后缀和。
所有需要取出的魔法豆总数=前缀和+后缀和-beans[i]*(len-i-1)。i为排序后当前元素的下标
代码：

class Solution {
    public long minimumRemoval(int[] beans) {
        if(beans.length==1) {
            return 0;
        }
        Arrays.sort(beans);
        //preSum[i] 表示 [0,i)的累加
        long[] preSum = new long[beans.length];
        //afterSum[i] 表示(i,len-1]的累加
        long[] afterSum = new long[beans.length];
        for(int i=1; i<beans.length; i++) {
            preSum[i] = preSum[i-1] + beans[i-1];
            afterSum[beans.length-1-i] = afterSum[beans.length-i] + beans[beans.length-i];
        }

        long res = Long.MAX_VALUE;
        for(int i=0; i<beans.length; i++) {
            res = Math.min(res, preSum[i] + afterSum[i] - (long) (beans.length - i - 1) *beans[i]);
        }
        return res;
    }
}