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

题目描述：

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

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

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

示例 1：

输入：beans = [4,1,6,5]
输出：4
解释：
- 我们从有 1 个魔法豆的袋子中拿出 1 颗魔法豆。
  剩下袋子中魔法豆的数目为：[4,0,6,5]
- 然后我们从有 6 个魔法豆的袋子中拿出 2 个魔法豆。
  剩下袋子中魔法豆的数目为：[4,0,4,5]
- 然后我们从有 5 个魔法豆的袋子中拿出 1 个魔法豆。
  剩下袋子中魔法豆的数目为：[4,0,4,4]
总共拿出了 1 + 2 + 1 = 4 个魔法豆，剩下非空袋子中魔法豆的数目相等。
没有比取出 4 个魔法豆更少的方案。

示例 2：

输入：beans = [2,10,3,2]
输出：7
解释：
- 我们从有 2 个魔法豆的其中一个袋子中拿出 2 个魔法豆。
  剩下袋子中魔法豆的数目为：[0,10,3,2]
- 然后我们从另一个有 2 个魔法豆的袋子中拿出 2 个魔法豆。
  剩下袋子中魔法豆的数目为：[0,10,3,0]
- 然后我们从有 3 个魔法豆的袋子中拿出 3 个魔法豆。
  剩下袋子中魔法豆的数目为：[0,10,0,0]
总共拿出了 2 + 2 + 3 = 7 个魔法豆，剩下非空袋子中魔法豆的数目相等。
没有比取出 7 个魔法豆更少的方案。

提示：

• 1 <= beans.length <= 10^5
• 1 <= beans[i] <= 10^5

---

解题分析及思路：

我们首先对袋子中的魔法豆数量进行升序排序。然后，我们计算所有袋子中魔法豆的总数 total。

接下来，我们使用贪心的策略来逐步减少 total，以满足条件。我们从最小的袋子开始，每次都尽量拿出最多的豆子，直到袋子中的豆子数达到平均值。

此过程可以理解为：

对于已经排序好的袋子，每次对于第i个袋子，以此袋子中的豆子数量作为标准：

• 比该袋子中豆子数量少的袋子（下标小于i）都拿出豆子，
• 比该袋子中豆子数量多的袋子（下标大于i）拿出部分豆子，直到该袋子中的豆子数量与第i个袋子中的豆子数量相等。

针对以上两种情况，可以优化为：以第 i 个袋子为标准时，最终只需保留 beans[i] * (n - i) 个豆子即可，即需要拿出 total - beans[i] * (n - i) 个豆子。

因此，我们可以遍历所有的袋子，以每个袋子作为标准，计算出此时需要拿出的豆子总数，取最小值即可。

func minimumRemoval(beans []int) int64 {
	sort.Ints(beans)
	var total int64
	for index := range beans {
		total += int64(beans[index])
	}
	min := func(i, j int64) int64 {
		if i > j {
			return j
		}
		return i
	}
	var res = total
	for index := range beans {
		res = min(res, total-int64(beans[index])*int64(len(beans)-index))
	}
	return res
}

复杂度：

• 时间复杂度：O(NlogN)，其中 N 为袋子的数量。排序的时间复杂度为 O(NlogN)。
• 空间复杂度：O(1)，只使用常数额外空间。

执行结果：

• 执行耗时:189 ms,击败了90.00% 的Go用户
• 内存消耗:8.2 MB,击败了95.00% 的Go用户