步道規劃 題解|APCS 2026 年 3 月高級 第 1 題
前置知識
這題是「二分搜答案」的標準題型,下面的講解直接把它當成已知,沒讀過的先讀:
- 二分搜答案:NTUCPC Guide〈對答案二分搜〉——「每段費用都不超過 \(L\) 做不做得到」有單調性,就能二分搜最小的可行 \(L\)。吳邦一《AP325》第 2 章「排序與二分搜」也有講。
簡潔題意
\(n\) 個地點各有座標 \(d_i\) 與高度 \(h_i\)。依座標由小到大排好後,分成恰好 \(k\) 段非空的連續區間;每段由左走到右,相鄰兩點的費用是座標差加上「高度增加量的兩倍」(下坡不加);段與段之間不走,只有一點的段費用是 \(0\)。求「各段費用的最大值」最小是多少(\(1 \le k \le n \le 10^5\),\(1 \le d_i, h_i \le 10^9\),所有 \(d_i\) 互異)。(APCS 逐筆給分。)
先把問題變成「一排非負的費用」
先依座標排序,算出每一步的費用 \(c_i\)(第 \(i - 1\) 點走到第 \(i\) 點):座標差加上 \(2 \times \max(0, h_i - h_{i-1})\),每一項都 \(\ge 0\)。切成 \(k\) 段就是在這 \(n - 1\) 步裡挑 \(k - 1\) 步不走,每段的費用是段內各步的和。
猜一個上限,貪心檢查做不做得到
固定上限 \(L\) 之後,從最左邊開始,能走就走:下一步走了會讓這一段超過 \(L\),就在這裡切開、從下一個點重新累積(切開的那一步不走、不收費)。這樣得到的段數是最少的——任何合法切法的第一段都不會比貪心的第一段長,把它的第一刀往右移到貪心的位置,後面只會少掉一些非負的費用,不會害後面超標;對剩下的部分重複同樣的論證。
貪心的段數 \(\le k\) 就代表 \(L\) 可行:段數不足時再多切幾刀即可,多切只會讓每段更便宜,而且 \(k \le n\) 一定切得出來。
二分搜最小的上限
\(L\) 越大越容易做到,所以在 \(0 \sim\)(全部費用總和)之間二分搜最小的可行 \(L\)。總和最大約 \(3 \times 10^{14}\)(\(10^5\) 步、每步最多 \(3 \times 10^9\)),費用、總和、\(L\) 都要用 long long。時間 \(O(n \log n + n \log(\text{總和}))\)。
#include <iostream>
#include <algorithm>
using namespace std;
const int MAX_N = 100000;
int n, k;
pair<long long, long long> spot[MAX_N]; // (座標, 高度),之後依座標排序
long long cost[MAX_N]; // cost[i]:從第 i-1 個點走到第 i 個點的費用
// 每段費用都不超過 limit 的話,最少要分成幾段?是否 <= k
bool feasible(long long limit) {
int groups = 1;
long long sum = 0; // 目前這一段已累積的費用
for (int i = 1; i < n; i++) {
if (sum + cost[i] > limit) {
groups++; // 在第 i 個點前面切開;跨段的這一步不走、不收費
sum = 0;
} else {
sum += cost[i];
}
}
return groups <= k;
}
int main() {
cin >> n >> k;
for (int i = 0; i < n; i++) cin >> spot[i].first;
for (int i = 0; i < n; i++) cin >> spot[i].second;
sort(spot, spot + n); // 依座標由小到大
long long total = 0;
for (int i = 1; i < n; i++) {
long long dist = spot[i].first - spot[i - 1].first;
long long climb = max(0LL, spot[i].second - spot[i - 1].second); // 下坡不收費
cost[i] = dist + 2 * climb;
total += cost[i];
}
// 答案介於 0 ~ total;limit 越大越容易做到,二分搜最小的可行 limit
long long low = 0, high = total;
while (low < high) {
long long mid = (low + high) / 2;
if (feasible(mid)) high = mid;
else low = mid + 1;
}
cout << low << '\n';
return 0;
}
測過再交:範例的數字都很小
兩個範例的座標、高度都只到 \(10\),答案是 \(2\) 和 \(7\)。沒蓋到的:只有一個點、每個點自己一段、大到超過 int 的費用,還有 \(n = 10^5\) 的大輸入。
| 輸入 | 正確輸出 | 這一筆在測什麼 |
|---|---|---|
1 1 / 7 / 3 |
0 |
最小的 \(n\):只有一個點,一步都不用走 |
3 3 / 5 1 3 / 1 1 1 |
0 |
\(k = n\):每個點自己一段,每段費用都是 \(0\) |
2 1 / 1 1000000000 / 1 1000000000 |
2999999997 |
一步的費用就超過 int:座標差 \(999999999\) 加上爬升 \(999999999\) 的兩倍 |
| 用程式造:\(n = 10^5\)、\(k = 1\),座標 \(10000, 20000, \ldots, 10^9\)(倒著給),高度 \(1, 10^9, 1, 10^9, \ldots\) 交替 | 100000999890000 |
總和約 \(10^{14}\):二分搜的範圍、累加都要 long long |
四筆都親眼看過正確,這題就穩了。
常犯錯誤
- 費用全部用
int:範例全過;自測表第 3 列會輸出0,本站 \(20\) 筆掛 \(11\) 筆。 - 二分搜的上界寫 \(10^9\):答案可以遠大於單一座標。範例全過;自測表第 3 列會輸出
1000000000,本站 \(20\) 筆掛 \(8\) 筆。 - 切開的那一步也收費(把它算進下一段的開頭):題目說段與段之間不走。範例 1 就會印
7。 - 貪心的段數「剛好等於 \(k\)」才算可行:段數比 \(k\) 少時多切幾刀就好,也要算可行。範例 1 就會印
27。