题目链接
Leetcode.2171 拿出最少数目的魔法豆 Rating ： 1748
题目描述
给你一个 正 整数数组 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
1beans.length105
-
1
1beans[i]105
解法：排序
我们先将豆子 beans按从小到大的顺序排序。
蓝色的就是要剩下来的豆子，白色的就是要拿走的豆子。
我们用 sum记录所有的豆子。
蓝色部分的豆子：
b
e
a
n
s
[
i
]
∗
(
n
−
i
)
beans[i] * (n – i)
beans[i]∗(n−i)
白色部分的豆子（要拿走的豆子）：
s
u
m
−
b
e
a
n
s
[
i
]
∗
(
n
−
i
)
sum – beans[i] * (n – i)
sum−beans[i]∗(n−i)
所以我们只需要从
i
=
0
i = 0
i=0遍历到
i
=
n
−
1
i = n – 1
i=n−1，遍历一遍，用一个 ans记录最小值即可。
时间复杂度：
O
(
n
∗
l
o
g
n
)
O(n * logn)
O(n∗logn)
C++代码：
using LL = long long;
class Solution {
public:
long long minimumRemoval(vectorint>& beans) {
LL sum = accumulate(beans.begin(),beans.end(),0LL);
sort(beans.begin(),beans.end());
int n = beans.size();
LL ans = 1e10;
for(int i = 0;i n;i++){
ans = min(ans , sum - (n - i) * 1LL * beans[i]);
}
return ans;
}
};
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
