周赛补题-Biweekly Contest 82

作者 Lucyyang 日期 2022-07-11
周赛补题-Biweekly Contest 82

深夜Biweekly Contest 82真是整人心态,不过题目还是很有趣的,稍微记录下最后两题。

2333. Minimum Sum of Squared Difference

题目:2333. Minimum Sum of Squared Difference。给定两个数组nums1和nums2以及k1+k2次操作(每次操作可以对任意元素加一或者减一),求出在操作数允许的范围内能够尽可能达到的最小平方和。

解法:注意到k1和k2的范围都在[0, 10^9],因此以O(k1+k2)的速度减少会TLE,我们发现进行一次操作只可能降低或者维持max(abs(nums1 - nums2))(绝对值之差最大的元素),我们可以通过二分来找到在操作数允许范围内的最大差值。注意找到最大差值之后,操作数可能还有剩余,这时分配给最大差值即可(需要排除掉最大差值为0的情况)。

代码:

class Solution:
def minSumSquareDiff(self, a: List[int], b: List[int], k1: int, k2: int) -> int:
n = len(a)
m = k1+k2
for i in range(n):
a[i] = abs(a[i]-b[i])
l = 0
r = 100000
while l < r:
mid = l + (r-l)//2
sum_ans = 0
for i in range(n):
if a[i] > mid:
sum_ans += a[i] - mid
if sum_ans <= m:
r = mid
else:
l = mid +1
sum_ans = 0
for i in range(n):
if a[i] > r:
sum_ans += a[i] - r
m -= sum_ans
res = 0
print(r, m)
for i in range(n):
if a[i] >= r:
if r != 0 and m > 0:
res += (r-1)*(r-1)
m -= 1
else:
res += r*r
else:
res += a[i]*a[i]
return res

2334. Subarray With Elements Greater Than Varying Threshold

题目:2334. Subarray With Elements Greater Than Varying Threshold