class Solution {
public:
long long minimumRemoval(vector<int>& beans) {
}
};
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 <= 1051 <= beans[i] <= 105原站题解
typescript 解法, 执行用时: 251 ms, 内存消耗: 65.7 MB, 提交时间: 2024-01-18 00:14:44
function minimumRemoval(beans: number[]): number {
let n = beans.length
beans.sort((a, b) => a - b);
let total = beans.reduce((a, b) => a + b, 0); // 豆子总数
let res = total; // 最少需要移除的豆子数
for (let i = 0; i < n; i++) {
res = Math.min(res, total - beans[i] * (n - i));
}
return res;
};
javascript 解法, 执行用时: 256 ms, 内存消耗: 66.2 MB, 提交时间: 2024-01-18 00:14:28
/**
* @param {number[]} beans
* @return {number}
*/
var minimumRemoval = function(beans) {
let n = beans.length
beans.sort((a, b) => a - b);
let total = beans.reduce((a, b) => a + b, 0); // 豆子总数
let res = total; // 最少需要移除的豆子数
for (let i = 0; i < n; i++) {
res = Math.min(res, total - beans[i] * (n - i));
}
return res;
};
python3 解法, 执行用时: 212 ms, 内存消耗: 28.5 MB, 提交时间: 2024-01-18 00:14:03
class Solution:
def minimumRemoval(self, beans: List[int]) -> int:
return sum(beans) - max((len(beans) - i) * v for i, v in enumerate(sorted(beans)))
rust 解法, 执行用时: 48 ms, 内存消耗: 3.5 MB, 提交时间: 2023-09-14 11:12:41
impl Solution {
pub fn minimum_removal(mut beans: Vec<i32>) -> i64 {
use std::cmp;
beans.sort();
let n = beans.len();
let mut s: i64 = 0;
let mut mx: i64 = 0;
for i in 0..n {
s += beans[i] as i64;
mx = cmp::max(mx, (n-i) as i64 * beans[i] as i64);
}
s - mx
}
}
java 解法, 执行用时: 40 ms, 内存消耗: 57.2 MB, 提交时间: 2023-09-14 10:59:52
class Solution {
public long minimumRemoval(int[] beans) {
long res = 0;
Arrays.sort(beans);
long sum = 0;
for(int i=0; i<beans.length; i++){
sum += beans[i];
long cur = (beans.length-i)*(long)beans[i];
res = Math.max(cur, res);
}
return sum-res;
}
}
java 解法, 执行用时: 42 ms, 内存消耗: 57 MB, 提交时间: 2023-09-14 10:58:51
class Solution {
public long minimumRemoval(int[] beans) {
int n = beans.length;
Arrays.sort(beans);
long sum = 0, mx = 0;
for ( int i = 0; i < n; ++i ) {
sum += beans[i]; // 豆子总数
mx = Math.max(mx, (long) (n-i) * beans[i]); // 可保留的豆子最大总数(以第i个袋子的数量为准)
}
return sum - mx;
}
}
python3 解法, 执行用时: 376 ms, 内存消耗: 28.2 MB, 提交时间: 2023-09-14 10:53:25
class Solution:
def minimumRemoval(self, beans: List[int]) -> int:
n = len(beans)
beans.sort()
total = sum(beans) # 豆子总数
res = total # 最少需要移除的豆子数
for i in range(n):
res = min(res, total - beans[i] * (n - i))
return res
cpp 解法, 执行用时: 224 ms, 内存消耗: 98.8 MB, 提交时间: 2023-09-14 10:52:58
class Solution {
public:
long long minimumRemoval(vector<int>& beans) {
int n = beans.size();
sort(beans.begin(), beans.end());
long long total = accumulate(beans.begin(), beans.end(), 0LL); // 豆子总数
long long res = total; // 最少需要移除的豆子数
for (int i = 0; i < n; ++i) {
res = min(res, total - (long long)beans[i] * (n - i));
}
return res;
}
};
golang 解法, 执行用时: 204 ms, 内存消耗: 8.9 MB, 提交时间: 2023-09-14 10:52:46
func minimumRemoval(beans []int) int64 {
sort.Ints(beans)
n := len(beans)
sum, mx := 0, 0
for i, v := range beans {
sum += v // 豆子总数
mx = max(mx, (n-i)*v) // 可保留的豆子最大总数(以第i个袋子的数量为准)
}
return int64(sum - mx)
}
func max(a, b int) int { if b > a { return b }; return a }
python3 解法, 执行用时: 236 ms, 内存消耗: 29.2 MB, 提交时间: 2023-09-14 10:50:36
class Solution:
def minimumRemoval(self, beans: List[int]) -> int:
# 袋子数量
n = len(beans)
# 排序
beans = sorted(beans)
# 总数
s = sum(beans)
# 第i个袋子豆子不变，最终可保留的豆子总数量
t = [(n-i) * v for i, v in enumerate(beans)]
return s - max(t)