【LeetCode】5691. 通过最少操作次数使数组的和相等

发表于 更新于 分类于 Valine：
本文字数： 385 阅读时长 ≈ 1 分钟

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

思路

贪心算法

设 $s1$ 和 $s2$ 分别是数组 $nums1$ 和 $nums2$ 的和。同时，保证 $s1<s2$ 

1
2
3
if (sum1 > sum2) {
    return minOperations(nums2, nums1);
}

为保证操作次数最小，应该尽量增加 $nums1$ 中元素的值，同时尽量减少 $nums2$ 中元素的值，因此：

  • $nums1$ 的每个元素$x$可以增加的量为 $6-x \in [0,5]$

  • $nums2$ 的每个元素$x$可以减少的量为 $x-1 \in [0,5]$

    记 $diff=s2-s1$，让 $nums1$ 中元素增加的值和 $nums2$ 中元素减少的值之和大于等于 $diff$ 。所以从数值5开始增加/减少量开始递减选取。

拓展

  1. accumulate累加求和

int sum1 = accumulate(nums1.begin(), nums1.end(), 0);
accumulate带有三个形参：头两个形参指定要累加的元素范围，第三个形参则是累加的初值。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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) {
            return 0;
        }
        if (sum1 > sum2) {
            return minOperations(nums2, nums1);
        }

        int diff = sum2 - sum1;
        vector<int> freq(6);
        for (int num: nums1) {
            ++freq[6 - num];
        }
        for (int num: nums2) {
            ++freq[num - 1];
        }

        int ans = 0;
        for (int i = 5; i >= 1 && diff > 0; --i) {
            while (freq[i] && diff > 0) {
                ++ans;
                --freq[i];
                diff -= i;
            }
        }

        return (diff > 0 ? -1 : ans);
    }
};