LeetCode：2171. 拿出最少数目的魔法豆（C++、Java 排序 + 前后缀）

本文主要是介绍LeetCode：2171. 拿出最少数目的魔法豆（C++、Java 排序 + 前后缀），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

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

题目描述：

实现原理与解析：

排序 + 前后缀

原理思路：

---

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 <= 105
• 1 <= beans[i] <= 105

实现原理与解析：

排序 + 前后缀

C++

class Solution {
public:long long minimumRemoval(vector<int>& beans) {int n = beans.size();sort(beans.begin(), beans.end());long long res = LONG_MAX;long long pre_sum = 0;vector<long long> suf(beans.size() + 1); // 后缀，表示以beans[i]为标准，需要去除的豆子个数long long j = 1; // 可以想象一下图，是很多矩形组成，这个j就是长度，差值是高度for (int i = n - 2; i >= 0; i--, j++) {suf[i] = (beans[i + 1] - beans[i]) * j + suf[i + 1];}for (int i = 0; i < n; i++) {long long cur = pre_sum;pre_sum += beans[i];res = min(res, cur + suf[i]);}return res;}
};

Java

class Solution {public long minimumRemoval(int[] beans) {Arrays.sort(beans);int n = beans.length;long[] suf = new long[n];long j = 1;for (int i = n - 2; i >= 0; i--, j++) {suf[i] = (beans[i + 1] - beans[i]) * j + suf[i + 1]; }long res = Long.MAX_VALUE;long pre = 0;for (int i = 0; i < n; i++) {long cur = pre;pre += beans[i];res = Math.min(res, cur + suf[i]);}return res;}
}

原理思路：

        理解题目，其实就算选中一个袋子，大于其豆子数量的袋子减去响应豆子变成和其一样的，小于的直接清零。所以很明显，我们需要排序。

        如果直接循环，根据数据范围，会超时，所以利用前后缀先预处理出选取不同i的前缀和，以及后缀，当然后缀取的是，需要去掉的豆子总和，在求后缀时，可以想象一下二维矩形图，其实是就是很多小矩形组成，这个j就是长度，差值是高度。

        这里我前缀直接在遍历的时候再求的，也可以提前求出来，是一样的。

        最后遍历一下就行，注意开long long。

这篇关于LeetCode：2171. 拿出最少数目的魔法豆（C++、Java 排序 + 前后缀）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---