---

[!info] related notes 算法面试题型 MOC 贪心算法

拿出最少数目的魔法豆

题目

2171. 拿出最少数目的魔法豆 - 力扣（LeetCode）

题解

我们可以将 beans 从小到大排序后，枚举最终非空袋子中魔法豆的数目 v，将小于 v 的魔法豆全部清空，大于 v 的魔法豆减少至 v，这样所有非空袋子中的魔法豆就都相等了。

由于拿出魔法豆 + 剩余魔法豆 = 初始魔法豆之和，我们可以考虑最多能剩下多少个魔法豆，从而计算出最少能拿出多少个魔法豆。

var minimumRemoval = function(beans) {
    beans = beans.sort((a,b) => a-b);
    let max = -Infinity;
    let sum = 0;
    for (let i = 0; i < beans.length; i++) {
        sum += beans[i];
        max = Math.max(max, beans[i] * (beans.length - i))
    }
    return sum - max;
};

参考

作者：灵茶山艾府 链接：https://leetcode.cn/problems/removing-minimum-number-of-magic-beans/solutions/1262419/pai-xu-hou-yi-ci-bian-li-by-endlesscheng-36g8/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。