2171. Removing Minimum Number of Magic Beans

2171. Removing Minimum Number of Magic Beans #

题目 #

You are given an array of positive integers beans, where each integer represents the number of magic beans found in a particular magic bag.

Remove any number of beans (possibly none) from each bag such that the number of beans in each remaining non-empty bag (still containing at least one bean) is equal. Once a bean has been removed from a bag, you are not allowed to return it to any of the bags.

Return the minimum number of magic beans that you have to remove.

Example 1:

Input: beans = [4,1,6,5]
Output: 4
Explanation:
- We remove 1 bean from the bag with only 1 bean.
  This results in the remaining bags: [4,0,6,5]
- Then we remove 2 beans from the bag with 6 beans.
  This results in the remaining bags: [4,0,4,5]
- Then we remove 1 bean from the bag with 5 beans.
  This results in the remaining bags: [4,0,4,4]
We removed a total of 1 + 2 + 1 = 4 beans to make the remaining non-empty bags have an equal number of beans.
There are no other solutions that remove 4 beans or fewer.

Example 2:

Input: beans = [2,10,3,2]
Output: 7
Explanation:
- We remove 2 beans from one of the bags with 2 beans.
  This results in the remaining bags: [0,10,3,2]
- Then we remove 2 beans from the other bag with 2 beans.
  This results in the remaining bags: [0,10,3,0]
- Then we remove 3 beans from the bag with 3 beans.
  This results in the remaining bags: [0,10,0,0]
We removed a total of 2 + 2 + 3 = 7 beans to make the remaining non-empty bags have an equal number of beans.
There are no other solutions that removes 7 beans or fewer.

Constraints:

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

题目大意 #

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

请你从每个袋子中 拿出 一些豆子(也可以 不拿出),使得剩下的 非空 袋子中(即 至少 还有 一颗 魔法豆的袋子)魔法豆的数目 相等 。一旦魔法豆从袋子中取出,你不能将它放到任何其他的袋子中。请你返回你需要拿出魔法豆的 最少数目。

提示:

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

解题思路 #

  • 这一题没有特别巧妙的方法。最初思路来源于暴力解法。从第一个袋子开始,依次以每个袋子中的豆子为基准,改变其他袋子里面的豆子数,使得其他袋子里面的豆子都和基准袋子中豆子一样多。
  • 如果从下标为 0 扫到下标 n-1 ,这中间会有大量重复计算。有些计算区间和的操作,反复计算了很多遍,导致算法不高效。由于移除豆子数量多少和基准袋豆子数量强相关,所以先排序。如果袋子内豆子数目小于基准袋的豆子,0 ≤ j < i,那么这些袋子内的豆子数量会归零。需要移除 beans[0] + beans[1] + ... + beans[i-1] 个豆子;如果袋子内豆子数目大于等于基准袋的豆子,j ≥ i ,那么这些袋子内的豆子需要调整为 beans[i] 个。需要移除 (beans[i] - beans[i]) + (beans[i+1] - beans[i]) + (beans[i+2] - beans[i]) + ... + (beans[n-1] - beans[i]) = beans[i]+ ... + beans[n-1] - (n-i) * beans[i] 个豆子。将这 2 种情况综合起来,那么总共需要移除 sum(beans) - (N - i) * beans[i] 个豆子。综上,先排序,然后从小到大扫一遍数组,动态维护最少移除豆子的个数即可。

代码 #

package leetcode

import "sort"

func minimumRemoval(beans []int) int64 {
	sort.Ints(beans)
	sum, mx := 0, 0
	for i, v := range beans {
		sum += v
		mx = max(mx, (len(beans)-i)*v)
	}
	return int64(sum - mx)
}

func max(a, b int) int {
	if b > a {
		return b
	}
	return a
}

⬅️上一页

下一页➡️

Calendar May 20, 2022
Edit Edit this page
本站总访问量:  次 您是本站第  位访问者