觀光旅遊 題解|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。