推 JIWP: 大師 08/07 00:30
※ 編輯: DJYOMIYAHINA (125.229.37.69 臺灣), 08/07/2024 00:32:09
推 oin1104: 大師 08/07 00:35
→ rainkaras: 大師 08/07 10:36
這應該是前天的
在整數域上的binary search 持續苦手
不過這題是有點更難了
照著答案寫
==
應該沒半天就忘了
一生就這樣了
def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
# 找出 cnt以及sums of subarrays which summations are <= S
def cnt_sum_of_subs_less_than_or_equal_S(S):
count, total_sum, current_window_sum, running_sum = 0, 0, 0, 0
start = 0
for end, num in enumerate(nums):
running_sum += num * (end - start + 1)
current_window_sum += num
while current_window_sum > S:
running_sum -= current_window_sum
current_window_sum -= nums[start]
start += 1
count += end - start + 1
total_sum += running_sum
return count, total_sum
# 找出sum是前K小個的subarr
def SumofKSmallestSubarrays(K):
# Binary search, K is 1-index
l,r = 0, sum(nums)+1
while l<r:
mid = (l+r)//2
cnt, sum_of_arrays = cnt_sum_of_subs_less_than_or_equal_S(mid)
if cnt < K:
l=mid+1
else:
r=mid
cnt, sum_of_arrays = cnt_sum_of_subs_less_than_or_equal_S(l)
# binary seach找到的l只是: sum(sub)<=S的sub個數>=K裡面的最小的S
# 但有可能有很多個subs的sum == S
# 所以這個cnt可能不是真的最小K個的sum
# 所以要另外減掉 (cnt-K)*S
# 若 cnt == K 則代表剛好只有一個subarr的sum==S
return sum_of_arrays - l*(cnt-K)
m = 10**9+7
ans = SumofKSmallestSubarrays(right)-SumofKSmallestSubarrays(left-1)
return ans % m
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 125.229.37.69 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1722961774.A.03D.html