3422. 將子數(shù)組元素變?yōu)橄嗟人璧淖钚〔僮鲾?shù)
為什么我沒(méi)想到把比中位數(shù)小的數(shù)和比中位數(shù)大的數(shù)分開(kāi)統(tǒng)計(jì)呢梗劫，如下是我的超時(shí)解
from sortedcontainers import SortedList
import bisect
import copy
class Solution:
def minOperations(self, nums: List[int], k: int) -> int:
a = nums[0:k]
b = set(a)
l = inf
if len(list(b)) == 1:
return 0
c = SortedList(a)
i = k
j = 0
if k%2 == 1:
d = c[k//2]
e = sum([abs(it-d) for it in c])
l = min([l,e])
while i < len(nums):
c.discard(nums[j])
c.add(nums[i])
d1 = d
d = c[k//2]
e -= abs(nums[j]- d1)
e += abs(nums[i] - d)
e2 = copy.deepcopy(c)
e2.discard(nums[i])
if d1 >= d:
x = bisect.bisect(e2,d1)
e += (k-1-x)*abs(d1-d)
y = bisect.bisect(e2,d)
e -= y*abs(d1-d)
e += sum([abs(e2[o]-d) - abs(e2[o]-d1) for o in range(y,x)])
else:
x = bisect.bisect(e2,d)
e -= (k-1-x)*abs(d1-d)
y = bisect.bisect(e2,d1)
e += y*abs(d1-d)
e += sum([abs(e2[o]-d) - abs(e2[o]-d1) for o in range(y,x)])
l = min([l,e])
i += 1
j += 1
if l == 0:
break
return l
else:
d = (c[k//2]+c[k//2-1])//2
e = sum([abs(it-d) for it in c])
l = min([l,e])
while i < len(nums):
c.discard(nums[j])
c.add(nums[i])
d1 = d
d = (c[k//2]+c[k//2-1])//2
e -= abs(nums[j]- d1)
e += abs(nums[i] - d)
e2 = copy.deepcopy(c)
e2.discard(nums[i])
if d1 >= d:
x = bisect.bisect(e2,d1)
e += (k-1-x)*abs(d1-d)
y = bisect.bisect(e2,d)
e -= y*abs(d1-d)
e += sum([abs(e2[o]-d) - abs(e2[o]-d1) for o in range(y,x)])
else:
x = bisect.bisect(e2,d)
e -= (k-1-x)*abs(d1-d)
y = bisect.bisect(e2,d1)
e += y*abs(d1-d)
e += sum([abs(e2[o]-d) - abs(e2[o]-d1) for o in range(y,x)])
l = min([l,e])
i += 1
j += 1
if l == 0:
break
return l
如下是網(wǎng)友的可通過(guò)解享甸，都想到一起了，但我沒(méi)想到分開(kāi)統(tǒng)計(jì)和
from sortedcontainers import * # SortedList
class Solution:
def minOperations(self, nums: List[int], k: int) -> int:
n = len(nums)
st = SortedList()
for i in range(k):
st.add(nums[i])
mid = st[(k - 1) // 2] # 中位數(shù)貪心
pre, suf = sum(st[: (k - 1) // 2 + 1]), sum(st[(k - 1) // 2 + 1 :])#動(dòng)態(tài)維護(hù)小于中位數(shù)的數(shù)字和梳侨，大于中位數(shù)的數(shù)字和
ans = suf - pre + int(k % 2 == 1) * mid
for i in range(k, n):
a, b = nums[i], nums[i - k]
st.add(a)
st.remove(b)
tmp = st[(k - 1) // 2]#新的中位數(shù)
cur = max(tmp, mid)#有可能中位數(shù)是被remove的蛉威，所以選二者較大值更新求和
if a <= mid and b <= mid:#如果都小于原中位數(shù)
pre = pre + a - b
elif a > mid and b > mid:#都大于中位數(shù)
suf = suf + a - b
elif a <= mid and b > mid:
pre = pre + a - cur
suf = suf - b + cur
else:
pre = pre - b + cur
suf = suf + a - cur
ans = min(ans, suf - pre + int(k % 2 == 1) * tmp)
mid = tmp
return ans
