题目描述

给你两个长度可能不等的整数数组 nums1 和 nums2。两个数组中的所有值都在 1 到 6 之间（包含 1 和 6）。

每次操作中，你可以选择 任意 数组中的任意一个整数，将它变成 1 到 6 之间 任意 的值（包含 1 和 6）。

请你返回使 nums1 中所有数的和与 nums2 中所有数的和相等的最少操作次数。如果无法使两个数组的和相等，请返回 -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]。

输入：nums1 = [1,1,1,1,1,1,1], nums2 = [6]
输出：-1
解释：没有办法减少 nums1 的和或者增加 nums2 的和使二者相等。

输入：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^5
• 1 <= nums1[i], nums2[i] <= 6

算法

(夹逼) $O(n \log n)$

1. 分别求出两个数组，其每种值的最少操作次数。
2. 对于一个数组，可以发现，操作 0 次的只能是其总和，操作 1 次可以达到的值的区间是 [sum - (max - 1), sum + (6 - min)]，即总和减去（最大的数字 - 1），到总和加上（6 减去最小的数字），区间中所有的值最少 1 次都可得到。依次类推，最少操作 2 次可达就是总和减去（最大的两个数字 - 2），到总和加上（12 - 最小的两个数字）。所以可以先将数组排序，然后求前缀和来得到最大的 i 个数字的和， 与最小的 i 个数字的和。
3. 将求得的一系列区间映射到一个 [0, 6 * n] 的数组上，并维护所有值的最少操作次数，具体见代码。
4. 然后枚举最终的值，求出得到这个值时，两个数组分别的最少操作次数。

时间复杂度

• 排序的时间复杂度为 $O(n \log n)$。
• 维护数组取值的时间复杂度为 $O(n)$，枚举答案的时间复杂度为 $O(n)$。
• 故总时间复杂度为 $O(n \log n)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储值的最少操作次数数组。

C++ 代码

class Solution {
private:
    void solve(vector<int> &res, const vector<int> &nums) {
        const int n = nums.size();
        vector<int> sum(n + 1, 0);
        for (int i = 1; i <= n; i++)
            sum[i] = sum[i - 1] + nums[i - 1];

        res[sum[n]] = 0;
        for (int i = 1; i <= n; i++) {
            int loss = sum[n] - sum[n - i] - i;
            int gain = 6 * i - sum[i];
            res[sum[n] - loss] = min(res[sum[n] - loss], i);
            res[sum[n] + gain] = min(res[sum[n] + gain], i);
        }

        // 维护每个值的最少操作次数。
        for (int i = 1; i < sum[n]; i++)
            res[i] = min(res[i], res[i - 1]);
        for (int i = 6 * n; i > sum[n]; i--)
            res[i] = min(res[i], res[i + 1]);
    }

public:
    int minOperations(vector<int>& nums1, vector<int>& nums2) {
        const int n = nums1.size(), m = nums2.size();
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());

        vector<int> res1(n * 6 + 10, n + 1), res2(m * 6 + 10, m + 1);
        solve(res1, nums1);
        solve(res2, nums2);

        int ans = INT_MAX;
        for (int i = max(n, m); i <= 6 * min(n, m); i++)
            ans = min(ans, res1[i] + res2[i]);

        if (ans == INT_MAX)
            return -1;

        return ans;
    }
};