本文涉及知识点

C++贪心

LeetCode1775. 通过最少操作次数使数组的和相等

给你两个长度可能不等的整数数组 nums1 和 nums2 。两个数组中的所有值都在 1 到 6 之间（包含 1 和 6）。
每次操作中，你可以选择 任意 数组中的任意一个整数，将它变成 1 到 6 之间 任意 的值（包含 1 和 6）。
请你返回使 nums1 中所有数的和与 nums2 中所有数的和相等的最少操作次数。如果无法使两个数组的和相等，请返回 -1 。
示例 1：
输入：nums1 = [1,2,3,4,5,6], nums2 = [1,1,2,2,2,2]
输出：3
解释：你可以通过 3 次操作使 nums1 中所有数的和与 nums2 中所有数的和相等。以下数组下标都从 0 开始。

• 将 nums2[0] 变为 6 。 nums1 = [1,2,3,4,5,6], nums2 = [6,1,2,2,2,2] 。
• 将 nums1[5] 变为 1 。 nums1 = [1,2,3,4,5,1], nums2 = [6,1,2,2,2,2] 。
• 将 nums1[2] 变为 2 。 nums1 = [1,2,2,4,5,1], nums2 = [6,1,2,2,2,2] 。
  示例 2：
  输入：nums1 = [1,1,1,1,1,1,1], nums2 = [6]
  输出：-1
  解释：没有办法减少 nums1 的和或者增加 nums2 的和使二者相等。
  示例 3：
  输入：nums1 = [6,6], nums2 = [1]
  输出：3
  解释：你可以通过 3 次操作使 nums1 中所有数的和与 nums2 中所有数的和相等。以下数组下标都从 0 开始。
• 将 nums1[0] 变为 2 。 nums1 = [2,6], nums2 = [1] 。
• 将 nums1[1] 变为 2 。 nums1 = [2,2], nums2 = [1] 。
• 将 nums2[0] 变为 4 。 nums1 = [2,2], nums2 = [4] 。
  提示：
  1 <= nums1.length, nums2.length <= 10⁵
  1 <= nums1[i], nums2[i] <= 6

C++贪心

如果nums1之和大于nums2之和，则交换之。
nums1[i]等于1和nums2[j]等于6的效果完全一样,都可以让差缩小1到5。
将所有6-nums1[i]，将所有nums[i]-1加到nums中。
need = $\sum$nums2-$\sum$nums1。
本题$⟺$ 从nums中选择最少的数，其和y大于等于need。 显然优先选择大数，否则交换，和更大。决策包容性
nums[i]等于x，可以增加[0,x]，故这些数可以增加[0,y]。

代码

核心代码

class Solution {
		public:
			int minOperations(vector<int>& nums1, vector<int>& nums2) {
				int sum1 = accumulate(nums1.begin(), nums1.end(), 0);
				int sum2 = accumulate(nums2.begin(), nums2.end(), 0);
				if (sum1 > sum2) {
					swap(sum1, sum2);
					swap(nums1, nums2);
				}
				int need = sum2 - sum1;
				vector<int> nums;
				for (const auto& n : nums1) {
					nums.emplace_back(6 - n);
				}
				for (const auto& n : nums2) {
					nums.emplace_back(n-1);
				}
				sort(nums.begin(), nums.end(), greater<>());
				int i = 0;
				const int N = nums.size();
				while ((i < N) && (need > 0)) {
					need -= nums[i]; i++;
				}
				if (need > 0) { return -1; }
				return i;
			}
		};

单元测试

vector<int> nums1,nums2;
		TEST_METHOD(TestMethod11)
		{
			nums1 = { 1, 2, 3, 4, 5, 6 }, nums2 = { 1, 1, 2, 2, 2, 2 };
			auto res = Solution().minOperations(nums1, nums2);
			AssertEx(3, res);
		}
		TEST_METHOD(TestMethod12)
		{
			nums1 = { 1,1,1,1,1,1,1 }, nums2 = {6 };
			auto res = Solution().minOperations(nums1, nums2);
			AssertEx(-1, res);
		}
		TEST_METHOD(TestMethod13)
		{
			nums1 = { 6,6 }, nums2 = { 1 };
			auto res = Solution().minOperations(nums1, nums2);
			AssertEx(3, res);
		}