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

本文主要是介绍2171.拿出最少数目的魔法豆，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

排序+前缀和+后缀和

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

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

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

原本魔法豆数量大于x：都变为x，假设有3个袋子数量大于x，那么就是这三个袋子魔法豆总数-3x，就是需要取出的魔法豆数量。
原本魔法豆数量小于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;}
}