# APCS實作題2026年3月中高級第1題：比例分割 > 日期：2026年3月10日 > 作者：王一哲 > [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=s179) ## 題目 ### 問題描述 小明有一個由 $n$ 個正整數組成的序列 $w_1, w_2, w_3, \dots, w_n$。他對序列中區間的「比例分割點」非常感興趣。 對於任何子區間 $[l, r]$，我們定義其區間和為 $S(l, r) = \sum_{i=l}^r w_i$，若 $l > r$，則 $S(l, r) = 0$。 現在小明有 $m$ 個詢問。每個詢問包含四個整數 $l, r, a, b$，請你找到一個唯一的分割點 $k$ ($l \leq k \leq r$)，使得該點滿足以下兩個條件： $$ \frac{S(l, k-1)}{S(l, r)} < \frac{a}{a+b} ~~~~~ \frac{S(l, k)}{S(l, r)} \geq \frac{a}{a+b} $$ 由於序列中的元素皆為**正整數**，可以保證對於每一組詢問，符合條件的 $k$ 恰好只有一個。 例如序列為 $2, 2, 6, 3, 1, 5$，當 $a = 1, b= 3$ 時，$k = 3$ 恰好會滿足條件。$S(1, 2) = 4, S(1, 3) = 10, S(1, 6) = 19$。 <br /> ### 輸入說明 第一行包含兩個整數 $n, m$ ($1 \leq n, m \leq 10^5$)，分別代表序列長度與詢問次數。 第二行包含 $n$ 個整數 $w_1, w_2, w_3, \dots, w_n$ ($1 \leq w_i \leq 10^4$)。 接下來的 $m$ 行，每行包含四個整數 $l, r, a, b$ ($1 \leq l \leq r \leq n, 1 \leq a \leq b \leq 10$)。 配分 - 40分：$1 \leq n, m \leq 10^3$ - 60分：無限制。 <br /> ### 輸出格式 對於每個詢問，輸出一行包含一個整數 $k$，即滿足條件的分割點索引。 <br /> ### 範例輸入1 ``` 6 1 2 2 6 3 1 5 1 6 1 1 ``` ### 範例輸出1 ``` 3 ``` ### 範例輸入2 ``` 12 3 1 4 2 3 6 7 1 9 9 8 10 6 4 10 1 6 1 6 1 10 3 11 6 8 ``` ### 範例輸出2 ``` 5 2 8 ``` <br /> ## Python 程式碼 我是用前綴和計算區間和，再對答案二分搜，速度不快，但是可以過關。費時最久約為 0.8 s，使用記憶體最多約為 15.8 MB，通過測試。 ```python= n, m = map(int, input().split()) # n 個數字，m 次詢問 psum = [0] + list(map(int, input().split())) # 暫存 n 個數字 for i in range(1, n+1): # 轉成前綴和 psum[i] += psum[i-1] for _ in range(m): # m 次詢問的條件 le, ri, a, b = map(int, input().split()) sum_le_ri = psum[ri] - psum[le-1] # S(l, r) ans = le # 答案 low, high = le, ri # 答案的下限、上限 while low <= high: # 對答案二分搜 mid = (high - low) // 2 + low sum_le_mid_n1 = psum[mid-1] - psum[le-1] # S(l, k-1) sum_le_mid = psum[mid] - psum[le-1] # S(l, k) cond1 = sum_le_mid_n1 * (a+b) < sum_le_ri * a # 條件 1 cond2 = sum_le_mid * (a+b) >= sum_le_ri * a # 條件 2 if cond1 and cond2: # 條件 1、2 皆成立，找到答案 ans = mid break elif not cond1: # 條件 1 不成立，mid 太右邊，降低上限 high = mid - 1 else: # 條件 2 不成立，mid 太左邊，提升上限 low = mid + 1 print(ans) ``` 用 sys.stdin.read() 一次讀取所有測資，費時最久約為 0.7 s，使用記憶體最多約為 34.8 MB，通過測試。 ```python= import sys data = sys.stdin.read().split() # 一次讀取所有測資 n, m = map(int, data[:2]) # n 個數字，m 次詢問 ptr = 2 psum = [0] + list(map(int, data[ptr:ptr+n])) # 暫存 n 個數字 ptr += n for i in range(1, n+1): # 轉成前綴和 psum[i] += psum[i-1] for _ in range(m): # m 次詢問的條件 le, ri, a, b = map(int, data[ptr:ptr+4]) ptr += 4 sum_le_ri = psum[ri] - psum[le-1] # S(l, r) ans = le # 答案 low, high = le, ri # 答案的下限、上限 while low <= high: # 對答案二分搜 mid = (high - low) // 2 + low sum_le_mid_n1 = psum[mid-1] - psum[le-1] # S(l, k-1) sum_le_mid = psum[mid] - psum[le-1] # S(l, k) cond1 = sum_le_mid_n1 * (a+b) < sum_le_ri * a # 條件 1 cond2 = sum_le_mid * (a+b) >= sum_le_ri * a # 條件 2 if cond1 and cond2: # 條件 1、2 皆成立，找到答案 ans = mid break elif not cond1: # 條件 1 不成立，mid 太右邊，降低上限 high = mid - 1 else: # 條件 2 不成立，mid 太左邊，提升上限 low = mid + 1 print(ans) ``` <br /><br /> ## C++ 程式碼 費時最久約為 25 ms，使用記憶體最多約為 1 MB，通過測試。 ```cpp= #include <cstdio> #include <vector> typedef long long LL; using namespace std; int main() { LL n, m; // n 個數字，m 次詢問 scanf("%lld %lld", &n, &m); vector<LL> psum (n+1, 0); // n 個數字，轉成前綴和 for(LL i=1; i<=n; i++) { LL w; scanf("%d", &w); psum[i] = psum[i-1] + w; } for(LL i=0; i<m; i++) { // m 次詢問的條件 LL le, ri, a, b; scanf("%lld %lld %lld %lld", &le, &ri, &a, &b); LL sum_le_ri = psum[ri] - psum[le-1]; // S(l, r) LL ans = le, low = le, high = ri; // 答案，答案的下限、上限 while(low <= high) { // 對答案二分搜 LL mid = (high - low) / 2 + low; LL sum_le_mid_n1 = psum[mid-1] - psum[le-1]; // S(l, k-1) LL sum_le_mid = psum[mid] - psum[le-1]; // S(l, k) bool cond1 = sum_le_mid_n1 * (a+b) < sum_le_ri * a; // 條件 1 bool cond2 = sum_le_mid * (a+b) >= sum_le_ri * a; // 條件 2 if (cond1 && cond2) { // 條件 1、2 皆成立，找到答案 ans = mid; break; } else if (!cond1) { // 條件 1 不成立，mid 太右邊，降低上限 high = mid - 1; } else { // 條件 2 不成立，mid 太左邊，提升上限 low = mid + 1; } } printf("%lld\n", ans); } return 0; } ``` <br /><br /> --- ###### tags:`APCS`、`Python`、`C++`