好几天前的
第一次认真去看segment tree在干嘛
以前的我只会逃避
现在我想去s
def numOfUnplacedFruits(self, fruits: List[int], baskets: List[int]) -> int:
n = len(fruits)
seg = [-1 for _ in range(4*n)]
def build(i, l, r):
if l==r:
seg[i] = baskets[l]
else:
mid = (l+r)//2
build(2*i, l, mid)
build(2*i+1, mid+1, r)
seg[i] = max(seg[2*i],seg[2*i+1])
def update(i, l, r, idx, val):
if idx<l or idx>r:
return
elif l==r:
baskets[idx] = val # query l==r, idx shoule equal to l and r
seg[i] = baskets[idx]
else:
mid = (l+r)//2
update(2*i, l, mid, idx, val)
update(2*i+1, mid+1, r, idx, val)
seg[i] = max(seg[2*i], seg[2*i+1])
def query(i, l, r, ql, qr):
if qr<l or ql>r:
return 0 # max(x,0)=x
elif ql<=l and qr>=r:
return seg[i]
else:
mid = (l+r)//2
return max(query(2*i, l, mid, ql, qr), query(2*i+1, mid+1, r, ql,
qr))
build(1, 0, n-1)
rets = 0
# TLE: 直接在外面再包一层binary search，整个超爆干花时间，O(N(logN)^2)?
# for f in fruits:
# # binary search
# l,r = 0, n-1
# while l<r:
# mid = (l+r)//2
# q_mid = query(1, 0, n-1, l, mid)
# if q_mid<f:
# l=mid+1
# else:
# r=mid
# if query(1, 0, n-1, l, l)<f:
# rets += 1
# else:
# update(1, 0, n-1, l, -1)
# 结合binary search跟query
def find_left(i, l, r, f):
if seg[i] < f:
return -1
if l == r:
return l
mid = (l + r) // 2
if seg[2*i] >= f:
return find_left(2*i, l, mid, f)
else:
return find_left(2*i+1, mid+1, r, f)
# 结合binary search跟query跟update
def find_and_use(i, l, r, fruit):
if seg[i] < fruit:
return -1
if l == r:
seg[i] = -1
return l
mid = (l + r) // 2
if seg[2*i] >= fruit:
res = find_and_use(2*i, l, mid, fruit)
else:
res = find_and_use(2*i+1, mid+1, r, fruit)
seg[i] = max(seg[2*i], seg[2*i+1])
return res
for f in fruits:
if find_and_use(1,0,n-1,f)==-1:
rets += 1
return rets