觀光旅遊 題解|APCS 2026 年 3 月中高級 第 2 題
前置知識
這題用到兩個基本工具,下面的講解直接把它們當成已知,沒讀過的先讀:
- 排序+二分搜:NTUCPC Guide〈排序〉與〈搜尋〉——排好序的陣列上,
lower_bound(x)回傳第一個 \(\ge x\) 的位置、upper_bound(x)回傳第一個 \(> x\) 的位置。吳邦一《AP325》第 2 章「排序與二分搜」。 - 整數溢位:語法書 2.9——
int大約只到 \(2.1 \times 10^9\),算出來的數超過就會溢位,要改用long long。
簡潔題意
\(n\) 位旅客各有抵達日,\(m\) 個行程各有閉區間 \([s_j, e_j]\),抵達日落在區間內的旅客就能參加這個行程。求「旅客、行程」合法配對的總數,同一天抵達的旅客分開算(\(1 \le n, m \le 10^5\),所有日期都在 \(1\) 到 \(10^8\) 之間,\(s_j \le e_j\))。
依正確通過的測試資料筆數給分,其中:
- 子題組 1(\(40\) 分):\(n, m \le 1000\)。
- 子題組 2(\(60\) 分):無額外限制。
先拿下 40 分:每個行程數一遍旅客
對每個行程,掃過全部旅客,抵達日在 \([s, e]\) 內就加一。\(O(nm)\),\(n, m \le 1000\) 時瞬間完成。
答案會多大?每位旅客最多配到 \(m\) 個行程,最多 \(n \times m = 10^{10}\) 組,超過 int,所以答案用 long long。
#include <iostream>
using namespace std;
const int MAX_N = 100000;
int n, m;
int day[MAX_N];
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) cin >> day[i];
long long answer = 0;
for (int j = 0; j < m; j++) {
int s, e;
cin >> s >> e;
for (int i = 0; i < n; i++)
if (s <= day[i] && day[i] <= e) answer++;
}
cout << answer << '\n';
return 0;
}
交上去,子題組 1 的 \(8\) 筆全對,穩拿 \(40\) 分;\(n, m\) 到 \(10^5\) 的測資大多會超時。
從 40 分到 100 分:旅客排序後,一個行程只要兩次二分搜
把抵達日排序。行程 \([s, e]\) 能接待的人數,就是「第一個大於 \(e\) 的位置」減「第一個不小於 \(s\) 的位置」,也就是 upper_bound(e) 減 lower_bound(s)。兩個端點用的函式不一樣:剛好在 \(s\) 那天和剛好在 \(e\) 那天抵達的人都要算進去。
排序 \(O(n \log n)\),每個行程兩次 \(O(\log n)\) 的二分搜,總共 \(O((n + m) \log n)\)。
#include <iostream>
#include <algorithm>
using namespace std;
const int MAX_N = 100000;
int n, m;
int day[MAX_N];
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) cin >> day[i];
sort(day, day + n);
long long answer = 0;
for (int j = 0; j < m; j++) {
int s, e;
cin >> s >> e;
// lower_bound:第一個 >= s 的位置;upper_bound:第一個 > e 的位置
int from = lower_bound(day, day + n, s) - day;
int to = upper_bound(day, day + n, e) - day;
answer += to - from; // 抵達日落在 [s, e] 的旅客人數
}
cout << answer << '\n';
return 0;
}
另一種寫法:門檻也排序,指標只往右走
不用二分搜也行。抵達日在 \([s, e]\) 的人數,等於「抵達日不超過 \(e\) 的人數」減掉「抵達日不超過 \(s - 1\) 的人數」。所有行程加起來,就是每個 \(e_j\) 各算一次前者、每個 \(s_j\) 各算一次後者——這兩組數可以分開算,所以把所有 \(e_j\) 排序、所有 \(s_j\) 也排序(拆開來排,誰跟誰是同一個行程已經不重要了)。門檻越來越大,旅客的指標只會往右走,排序之後兩輪各 \(O(n + m)\)。
#include <iostream>
#include <algorithm>
using namespace std;
const int MAX_N = 100000;
int n, m;
int day[MAX_N];
int s[MAX_N], e[MAX_N];
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) cin >> day[i];
for (int j = 0; j < m; j++) cin >> s[j] >> e[j];
sort(day, day + n);
// 每個行程的人數=「抵達日 <= e 的人數」減「抵達日 <= s - 1 的人數」。
// 兩組門檻各自排序後,旅客的指標只會往右走,不必每次從頭數。
sort(s, s + m);
sort(e, e + m);
long long answer = 0;
int ptr = 0;
for (int j = 0; j < m; j++) {
while (ptr < n && day[ptr] <= e[j]) ptr++;
answer += ptr; // 抵達日 <= e[j] 的人數
}
ptr = 0;
for (int j = 0; j < m; j++) {
while (ptr < n && day[ptr] < s[j]) ptr++;
answer -= ptr; // 抵達日 < s[j](也就是 <= s[j] - 1)的人數
}
cout << answer << '\n';
return 0;
}
測過再交:範例沒有同一天抵達的旅客
範例的三位旅客抵達日都不一樣,每個行程都至少有一個人參加,答案只有 \(6\)。沒蓋到的:同一天抵達的旅客、沒有人能參加的行程、日期的兩個極端,以及超過 int 的答案。
| 輸入 | 正確輸出 | 這一筆在測什麼 |
|---|---|---|
3 3 / 4 4 4 / 4 4 / 1 3 / 5 100000000 |
3 |
三位旅客同一天抵達要分開算;後兩個行程一個人都沒有 |
2 2 / 100000000 1 / 1 1 / 100000000 100000000 |
2 |
日期的兩個極端、只有一天的行程 |
用程式造:\(n = m = 10^5\),抵達日全是 1,行程全是 1 1 |
10000000000 |
答案最大,超過 int |
三筆都親眼看過正確,這題就穩了。
常犯錯誤
- 答案用
int:範例全過;自測表第 3 列印1410065408,本站 \(20\) 筆掛 \(8\) 筆。 - 右端點用
lower_bound(e):剛好在 \(e\) 那天抵達的人被漏掉,範例印5。 - 左端點用
upper_bound(s)(或自己掃的時候寫成「抵達日 \(> s\) 才算」):剛好在 \(s\) 那天抵達的人被漏掉,範例印4。 - 忘了先排序抵達日:
lower_bound、upper_bound只能用在排好序的陣列上,範例印8。 - 用日期當陣列索引做差分(每個行程在 \(s\) 加一、在 \(e + 1\) 減一,再對抵達日查次數):日期最大到 \(10^8\),光是這個
int陣列就要約 \(400\) MB,超過這題的記憶體限制 \(256\) MB。