P1 比例分割

思路

题目有提到兩個關鍵比較規則

• S(l,k-1)/S(l,r)<a/a+b
• S(l,k)/S(l,r)>=a/a+b

那我們可以推測:

• 假如S(l,k-1)/S(l,r)>=a/a+b代表S(l,k-1)過大，l到k的範圍需要縮小
• 假如S(l,k)/S(l,r)<a/a+b代表S(l,k-1)過小，l到k的範圍需要放大

演算法:

• 因為一個一個試會時間爆掉，所以使用二分搜去夾出答案
• 如果每次都去累加則會造成重複執行太多次一樣的動作，所以我們可以使用前啜和去解決這個問题
• 如果找到可行的答案，則進行減枝，減少運行次數

AC code

from sys import stdin
n,m=map(int,stdin.readline().strip().split())
w=list(map(int,stdin.readline().strip().split()))
data=[list(map(int,stdin.readline().strip().split())) for _ in range(m)]
presum=[0]*(n+1)
for i in range(1,n+1):
    presum[i]=presum[i-1]+w[i-1]
#print(presum)
def find(l,r,a,b):
    def solve(l,r,a,b,k):
        global_num=a/(a+b)
        allsum=presum[r]-presum[l-1]
        x=presum[k-1]-presum[l-1]
        y=presum[k]-presum[l-1]
        if x/allsum>=global_num:
            return 0
        elif y/allsum<global_num:
            return 1
        else:
            return 2
    L=l
    R=r
    while L<R:
        mid=(L+R)//2
        current=solve(l,r,a,b,mid)
        if current==0:
            R=mid
        elif current==1:
            L=mid+1
        elif current==2:
            return mid
    return L
for l,r,a,b in data:
    print(find(l,r,a,b))

P2 觀光旅遊

思路(離散化+差分):

• 先把出發時間排序，方便進行二分搜查詢
• 對於m個表演進行離散化，創立一個長度為n的陣列diff，把diff[bisect_left(出發時間,起始時間)]+1，diff[bisect_right(出發時間,結束時間)] (要bisect_left(出發時間,起始時間)<=bisect_right(出發時間,結束時間)才成立)
• 最後對diff做前啜和即可得出答案

AC code

from sys import stdin
import bisect
n,m=map(int,stdin.readline().strip().split())
t=list(map(int,stdin.readline().strip().split()))
data=[list(map(int,stdin.readline().strip().split())) for _ in range(m)]
t.sort()
diff=[0]*(n+1)
for i in data:
    L=bisect.bisect_left(t,i[0])
    R=bisect.bisect_right(t,i[1])-1
    if L<=R:
        diff[L]+=1
        diff[R+1]-=1
ans=0
current=0
for i in range(n):
    current+=diff[i]
    ans+=current
print(ans)