作者：小迅
链接：https://leetcode.cn/problems/equal-sum-arrays-with-minimum-number-of-operations/solutions/2010289/tan-xin-zhu-shi-chao-ji-xiang-xi-by-xun-tjs4r/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 

题目

示例

思路

题意 -> 我们将两个数组中的任意元素进行变化，使得两个数组的和相等，返回最小的变化次数

对于最值问题我们使用贪心作为切入点，对于本题我们可以将所有元素进行累加，然后再变化具体元素时，我们每次都寻找最大或者最小值进行变化，这样可以使得每次的变化值能辐射的范围更大，也就更能匹配正确值。

我们不妨设 s1 > s2, 则两个数组的差值为d = s1 - s2。为了使操作次数最少，我们贪心的把nums1中比较大的数变成1,把对应的nums2中比较小的数变成6，每一次变化把答案+1，直到d小于等于0。当 d 小于 0 时，说明我们本次修改的辐射范围为 小于 0的位置，自然也就包含0

代码

int min_operations(int *cnt1, int *cnt2, int d)
{
    int i, ans = 0;

    for (i = 6; i > 1 && d > 0; i--) {
        while (d > 0 && cnt1[i]) {//最大值变小
            d -= i - 1;
            cnt1[i]--;
            ans++;
        }
        while (d > 0 && cnt2[7 - i]) {//最小值变大
            d -= i - 1;
            cnt2[7 - i]--;
            ans++;
        }
    }
    return ans;
}

int minOperations(int* nums1, int nums1Size, int* nums2, int nums2Size){
    int i, d = 0, cnt1[7] = {0}, cnt2[7] = {0};
    /* 无法使两个数组的和相等 */
    if (nums1Size > 6 * nums2Size || nums2Size > 6 * nums1Size)
        return -1;
    
    for (i = 0; i < nums1Size; i++) {//累加nums1的前缀和
        cnt1[nums1[i]]++;
        d += nums1[i];
    }
    for (i = 0; i < nums2Size; i++) {//可以累加也可以相差
        cnt2[nums2[i]]++;
        d -= nums2[i];
    }

    if (d < 0)
        return min_operations(cnt2, cnt1, -d);//返回修改操作数
    return min_operations(cnt1, cnt2, d);
}


作者：小迅
链接：https://leetcode.cn/problems/equal-sum-arrays-with-minimum-number-of-operations/solutions/2010289/tan-xin-zhu-shi-chao-ji-xiang-xi-by-xun-tjs4r/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。