1. 题目
给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，长度为 n 。
数组 nums1 和 nums2 的 差值平方和 定义为所有满足 0 <= i < n 的 (nums1[i] - nums2[i])^2 之和。
同时给你两个正整数 k1 和 k2 。你可以将 nums1 中的任意元素 +1 或者 -1 至多 k1 次。
类似的，你可以将 nums2 中的任意元素 +1 或者 -1 至多 k2 次。
请你返回修改数组 nums1 至多 k1 次且修改数组 nums2 至多 k2 次后的最小 差值平方和 。
注意：你可以将数组中的元素变成 负 整数。
示例 1：
输入：nums1 = [1,2,3,4], nums2 = [2,10,20,19], k1 = 0, k2 = 0
输出：579
解释：nums1 和 nums2 中的元素不能修改，因为 k1 = 0 和 k2 = 0 。
差值平方和为：(1 - 2)^2 + (2 - 10)^2 + (3 - 20)^2 + (4 - 19)^2 = 579 。
示例 2：
输入：nums1 = [1,4,10,12], nums2 = [5,8,6,9], k1 = 1, k2 = 1
输出：43
解释：一种得到最小差值平方和的方式为：
- 将 nums1[0] 增加一次。
- 将 nums2[2] 增加一次。
最小差值平方和为：
(2 - 5)^2 + (4 - 8)^2 + (10 - 7)^2 + (12 - 9)^2 = 43 。
注意，也有其他方式可以得到最小差值平方和，但没有得到比 43 更小答案的方案。
提示：
n == nums1.length == nums2.length
1 <= n <= 10^5
0 <= nums1[i], nums2[i] <= 10^5
0 <= k1, k2 <= 10^9
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimum-sum-of-squared-difference
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题
- 答案只与 对应元素的 非零 绝对值 有关系
- 对这些绝对值进行排序，大的优先减少
class Solution:
def minSumSquareDiff(self, nums1: List[int], nums2: List[int], k1: int, k2: int) -> int:
diff = list(filter(lambda x : x!=0, [abs(x-y) for x, y in zip(nums1, nums2)]))
# 非零 绝对值
diff.sort(reverse=True) # 逆序排列
if len(diff) == 0:
return 0
k = k1+k2 # 总的调整次数
diff.append(0) # 代码编写简单需要
prevnum = diff[0]
ct = 1 # 前面相同元素的个数
i = 0
while i < len(diff)-1:
delta = diff[i]-diff[i+1] # 跟后一个的差值
if delta == 0:
ct += 1 # 相同值的元素个数 + 1
else: # 遇到有下降台阶了
if k >= delta*ct: # k 的次数，够ct个数降到下个元素的值
prevnum = diff[i+1]
k -= delta*ct
ct += 1
else: # 不够， 结束了
delta = k//ct # 把剩余的 k 次 均匀分给 ct 个数
prevnum -= delta # 每个数还能降低 delta
left = k - delta*ct # 剩余的次数，每个数的值还能 -1
return int(math.pow((prevnum-1), 2)*left + math.pow(prevnum, 2)*(ct-left) + sum([x*x for x in diff[ct:]]))
i += 1
return 0
188 ms 31.4 MB Python3
1648 题是一样的思路，可以试试
https://leetcode.cn/problems/sell-diminishing-valued-colored-balls/
我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！
