本文涉及的基础知识点

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

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会被淘汰。所以有相等的值不影响最终结果。

2024年10月11补充

最终豆子的数量只有两种：0,x。
且初始状态下一定有某袋豆子数量为x，下面用反证法证明。
一，如果袋子中豆子的数量都小于x，由于豆子只能减少不能增加，故不会有袋子的数量为x。此种情况不存在。
二，令初始状态下，豆子数量大于x的最小数量为x1，则x =x1是更优解。
对豆子数量排序，枚举x。令数量大于等于x的数量为n1，则剩余豆子数量为：x$\times$n1。
本题解为：袋子的总数量-max(x$\times$n1)。

代码

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

核心代码

	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);
		}