比例分割 題解|APCS 2026 年 3 月中高級 第 1 題
前置知識
這題用到三個基本工具,下面的講解直接把它們當成已知,沒讀過的先讀:
- 前綴和:NTUCPC Guide〈前綴和〉——先算 \(P_i = w_1 + \cdots + w_i\),任何一段的和就是 \(P_r - P_{l-1}\),一次 \(O(1)\)。
- 二分搜:NTUCPC Guide〈搜尋〉——在「先全部不成立、後全部成立」的序列上找第一個成立的位置。吳邦一《AP325》第 2 章「排序與二分搜」也有講。
- 整數溢位:語法書 2.9——
int大約只到 \(2.1 \times 10^9\),算出來的數超過就會溢位,要改用long long。
簡潔題意
給一個正整數序列 \(w_1, w_2, \ldots, w_n\) 和 \(m\) 個詢問。每個詢問給 \(l, r, a, b\),要找最小的 \(k\)(\(l \le k \le r\)),使 \(w_l + \cdots + w_k\) 至少是整段 \(w_l + \cdots + w_r\) 的 \(\dfrac{a}{a + b}\)(\(1 \le n, m \le 10^5\),\(1 \le w_i \le 10^4\),\(1 \le a \le b \le 10\))。
依正確通過的測試資料筆數給分,其中:
- 子題組 1(\(40\) 分):\(n, m \le 1000\)。
- 子題組 2(\(60\) 分):無額外限制。
先拿下 40 分:每個詢問從 \(l\) 往右加
先把整段的和 total 算出來,再從 \(l\) 開始一個一個加,第一次達到比例就停。加到 \(r\) 時加起來就是整段的和,一定達標,所以迴圈一定會停。每個詢問最多掃 \(n\) 個數,\(O(nm)\),\(n, m \le 1000\) 時綽綽有餘。
「至少 \(\dfrac{a}{a + b}\)」不要用除法算:\(\dfrac{\text{part}}{\text{total}} \ge \dfrac{a}{a + b}\) 兩邊同乘 \((a + b) \times \text{total}\),就是 \(\text{part} \times (a + b) \ge \text{total} \times a\),全部是整數、沒有小數誤差。
乘出來會多大?total 最大是 \(10^5 \times 10^4 = 10^9\),part 不超過 total,再乘上 \(a + b \le 20\),最大 \(2 \times 10^{10}\),超過 int,所以用 long long。
#include <iostream>
using namespace std;
const int MAX_N = 100000;
int n, m;
int w[MAX_N + 1];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> w[i];
while (m--) {
int l, r, a, b;
cin >> l >> r >> a >> b;
long long total = 0;
for (int i = l; i <= r; i++) total += w[i];
long long part = 0;
int k = l;
while (true) {
part += w[k];
if (part * (a + b) >= total * a) break; // 從 l 加到 k 已經達到 a/(a+b)
k++;
}
cout << k << '\n';
}
return 0;
}
交上去,子題組 1 的 \(8\) 筆全對,穩拿 \(40\) 分;\(n, m\) 到 \(10^5\) 的測資大多會超時。
從 40 分到 100 分:前綴和+二分搜
慢的地方有兩個:每個詢問都重新加一次整段,又從 \(l\) 一格一格往右找。
整段的和用前綴和:先算 prefix[i] \(= w_1 + \cdots + w_i\),從 \(l\) 加到 \(k\) 就是 prefix[k] - prefix[l - 1],一次 \(O(1)\)。
往右找改成二分搜:\(w_i\) 都是正的,\(k\) 越大、從 \(l\) 加到 \(k\) 的和越大,所以「有沒有達標」隨著 \(k\) 變大只會從否變成是、不會再變回來。在 \([l, r]\) 上二分搜第一個達標的 \(k\);\(k = r\) 一定達標,答案一定在這個範圍裡。每個詢問 \(O(\log n)\),總共 \(O(n + m \log n)\)。
#include <iostream>
using namespace std;
const int MAX_N = 100000;
int n, m;
long long prefix[MAX_N + 1]; // prefix[i] = w_1 + ... + w_i
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
int w;
cin >> w;
prefix[i] = prefix[i - 1] + w;
}
while (m--) {
int l, r, a, b;
cin >> l >> r >> a >> b;
long long total = prefix[r] - prefix[l - 1];
// 找最小的 k,使 (從 l 加到 k 的和) * (a + b) >= total * a
int low = l, high = r;
while (low < high) {
int mid = (low + high) / 2;
long long part = prefix[mid] - prefix[l - 1];
if (part * (a + b) >= total * a) high = mid; // mid 已達標,答案在 mid 或更左
else low = mid + 1; // 還不夠,答案在 mid 右邊
}
cout << low << '\n';
}
return 0;
}
測過再交:範例沒有剛好達到比例的詢問
兩個範例的四個詢問,門檻都不是整數(所以沒有「剛好等於」的情況),答案也都不在區間的兩端;把門檻的小數捨掉、或整段的和忘了扣掉 \(l\) 前面,這四個詢問的答案剛好都不變。數字也都很小,乘出來不會超過 int。
| 輸入 | 正確輸出 | 這一筆在測什麼 |
|---|---|---|
2 1 / 1 1 / 1 2 1 1 |
1 |
前一項剛好是整段的一半:「至少」包含等於 |
3 1 / 1 1 3 / 1 3 1 2 |
2 |
門檻是 \(5 / 3\),不是整數 |
3 1 / 10 1 1 / 2 3 1 2 |
2 |
\(l\) 前面有一個很大的數:整段的和要扣掉它 |
3 3 / 1 1 5 / 1 3 1 1 / 2 3 1 10 / 3 3 1 1 |
3 / 2 / 3 |
答案在 \(r\)、答案在 \(l\)、\(l = r\):二分搜的兩端 |
用程式造:\(n = m = 10^5\),\(w_i\) 全是 \(10^4\),每個詢問都是 1 100000 1 10 |
每行都是 9091 |
乘出來超過 int,也是最大的輸入 |
五筆都親眼看過正確,這題就穩了。
常犯錯誤
- 「至少」寫成嚴格大於(
part * (a + b) > total * a):範例全過;自測表第 1 列印2,本站 \(20\) 筆掛 \(12\) 筆。 - 用整數除法算門檻(
part >= total * a / (a + b)):小數被捨掉,門檻變低。範例全過;自測表第 2 列印1,本站 \(20\) 筆掛 \(8\) 筆。 - 整段的和忘了扣掉 \(l\) 前面(
total = prefix[r]):兩個範例剛好都不受影響,範例全過;自測表第 3 列印3,本站 \(20\) 筆掛 \(8\) 筆。 - 二分搜的右界設成 \(r - 1\):答案是 \(r\) 的詢問找不到。範例全過;自測表第 4 列第 1 行印
2,本站 \(20\) 筆掛 \(3\) 筆。 - 前綴和、整段的和都用
int:它們本身放得下(最大 \(10^9\)),乘上 \(a + b\) 就溢位。範例全過;自測表第 5 列印出來全是48137,本站 \(20\) 筆掛 \(7\) 筆。