【C++前缀和排序】2171. 拿出最少数目的魔法豆|1748

本文涉及的基础知识点

C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例包括课程视频

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

难度分：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 <= beans.length <= 10⁵
1 <= beans[i] <= 10⁵

前缀和+排序

n = beans.size()
最后各袋的魔法豆数量一定: x和0。且x $\in$ beans。
枚举nums[i]等于x。
nums[0…i-1]全部清零, nums[i…]全部减少为x。
即：preSum.back() - ( n- i)(long long nums[i])
其实不需要求前缀和，只需要求和就可以了。
如果有多个nums[i]等于x，非最大下标i会被淘汰。所以有相等的值不影响最终结果。

代码

打开打包代码的方法兼述单元测试

核心代码

	class Solution {public:long long minimumRemoval(vector<int>& beans) {sort(beans.begin(), beans.end());long long total = accumulate(beans.begin(), beans.end(), 0LL);long long llMax = 0;for (int i = 0; i < beans.size(); i++) {llMax = max((long long)llMax, (long long)beans[i] * ((long long)beans.size()-i));}return total - llMax;}};

单元测试

vector<int> beans;TEST_METHOD(TestMethod11){beans = { 4, 1, 6, 5 };auto res = Solution().minimumRemoval(beans);AssertEx(4LL, res);}TEST_METHOD(TestMethod12){beans = { 2,10,3,2 };auto res = Solution().minimumRemoval(beans);AssertEx(7LL, res);}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功