APCS 2025/3月中高級解題紀錄

太久沒發東西了，那就來發個APCS好了 :D
是說我的程式碼很醜，已經被淳嫌過 遍了，因為我懶著空格，然後變數什麼的名子都亂取owo，但我會把這習慣改掉的嗚嗚嗚，然後因為我這程式碼是之前寫得然後我懶著加空格，所以看時記得做好心理準備，反正我看得懂。

1.比例分割

題目點這
簡單來說就是題目有 個詢問包含四整數 ，然後要找一個分割點 滿足

這題涉及到前綴和與二分搜，我的解題思路是輸入完 個整數以後先直接做前綴和，也就是跑一個 for 迴圈

for i in range(1, n):
    w[i] += w[i - 1]

，接著要求 就能以 的方式算出。
然後後面就可以進行二分搜尋找剛好符合上面那個條件
最後總時間複雜度 。

n,m=map(int,input().split())
w=[0]+list(map(int,input().split()))
for i in range(2,n+1):
    w[i]+=w[i-1]

def owo(left,right):
    global a,b,l,r
    if left==right:
        return left
    mid=(left+right)//2
    if (w[mid-1]-w[l-1])*(a+b)>=a*(w[r]-w[l-1]):
        return owo(left,mid-1)
    elif (w[mid]-w[l-1])*(a+b)<a*(w[r]-w[l-1]):
        return owo(mid+1,right)
    else:
        return mid

for _ in range(m):
    l,r,a,b=map(int,input().split())
    print(owo(l,r))

2.觀光旅遊

題目點這
題目在說有 個不同的旅行團。第 個旅行團預計在第 天抵達觀光景點，接著還有 個表演，每個表演各有開始表演的時間（天）和結束表演的時間（天），每個表演在該表演會表演的時段中每天都會表演一場，且表演的時後不會跟其他表演重複，就代表如果一天有123個表演然後那天剛好有旅行團，那那個旅行團在這一天就一定可以看完這123個表演。 :D
這題我覺得相對簡單，我的做法是用事件排序的方式處理。輸入完資料後先把所有時間點依照事件種類標記：表演開始的時間標記成 0，表演結束的時間標記成 2，觀光團抵達的時間則標記成 1。這樣 sort 之後就可以保證開始事件會先處理，再處理觀光團，最後處理結束事件，避免邊界情況搞錯。
接著就進入到 for 迴圈環節，遇到表演開始事件時，就代表目前多了一個正在表演的表演團，然後遇到觀光團抵達時，此時 count 就代表目前正在表演的團體數量，因此直接累加到 total 中即可，若遇到表演結束事件，則將 count 減一。
最後時間複雜度為

n,m=map(int,input().split())
t=list(map(int,input().split()))
p=[list(map(int,input().split())) for _ in range(m)]
total=0
count=0
l=[]
for i in range(m):
    l.append([p[i][0],0])
    l.append([p[i][1],2])
for i in range(n):
    l.append([t[i],1])
l.sort()
for i in range(len(l)):
    if l[i][1]==0:
        count+=1
    elif l[i][1]==2:
        count-=1
    else:
        total+=count
print(total)

3.校運代表隊

題目點這
這題等我學會dfs再說吧 :D