機器出租 題解｜APCS 2023 年 1 月高級 第 4 題

前置知識

這題是「活動選擇」加上多台機器，下面的講解直接把這些當成已知，沒讀過的先讀；同一個主題兩邊都有的，對照著讀會更快上手：

• 依結束時間排序的貪心（活動選擇）：吳邦一《AP325》第 4 章的 P-4-4「幾場華山論劍」就是本題 \(k = 1\) 的版本（教材 PDF 第 127～129 頁），「先選最早結束的為什麼不會吃虧」那裡有完整證明；NTUCPC Guide〈貪心法 I〉補齊「貪心法是什麼、什麼時候會失敗」。
• multiset：NTUCPC Guide〈Set 與 Map〉——會放、會刪、會用 lower_bound 找「第一個不小於 \(x\) 的元素」就夠；本題用它管 \(k\) 台機器各自的結束時間。
• 用 pair 排序：要優先比較的值放在 first。

簡潔題意

\(k\) 台一樣的機器、\(n\) 筆租借申請，第 \(i\) 筆要從時刻 \(L_i\) 用到 \(R_i\)（兩端都算在內）。一台機器同一時刻只能給一筆申請用，所以同一台機器上前一筆在 \(R\) 結束，下一筆的開始時間必須嚴格大於 \(R\)。可以拒絕任何申請，問最多能接幾筆（\(1 \le n \le 10^5\)，\(1 \le k \le 100\)，\(0 \le L_i \le R_i \le 10^8\)）。

依正確通過的測試資料筆數給分，其中：

• 子題組 1（\(20\) 分）：\(n \le 100\)，\(k = 1\)。
• 子題組 2（\(20\) 分）：\(k = 1\)。
• 子題組 3（\(60\) 分）：無額外限制。

先拿下 40 分：一台機器就是活動選擇

只有一台機器時，題目就是「數線上一堆線段，最多挑幾條兩兩不碰」——活動選擇。把申請依結束時間由小到大排好，從頭掃過去：接得上（開始時間 \(>\) 上一筆接受的結束時間）就接，接不上就跳過。先接最早結束的為什麼不吃虧：它結束得最早，留給後面的時間最多，任何最佳方案的第一筆換成它都不會變差。子題組 1 的 \(n \le 100\) 是留給枚舉所有子集合或 \(O(n^2)\) 做法的，但貪心本來就是 \(O(n \log n)\)，兩個子題組一起拿。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;                               // 這兩個子題組 k = 1
    vector<int> l(n), r(n);
    for (int &v : l) cin >> v;
    for (int &v : r) cin >> v;

    vector<pair<int, int>> job(n);               // (結束時間, 開始時間)：sort 會先比結束時間
    for (int i = 0; i < n; i++) job[i] = {r[i], l[i]};
    sort(job.begin(), job.end());

    int count = 0, last = -1;                    // last：機器上一筆申請的結束時間，-1 ＝ 還沒用過
    for (int i = 0; i < n; i++) {
        int start = job[i].second, finish = job[i].first;
        if (start > last) {                      // 要嚴格晚於上一筆的結束時間才接得上
            count++;
            last = finish;
        }
    }
    cout << count << '\n';
    return 0;
}

每筆申請存成 (結束時間, 開始時間)，sort 比 pair 會先比 first，正好依結束時間排。範例 1 排好是 \([0,2]\)、\([2,3]\)、\([3,4]\)、\([1,5]\)、\([4,6]\)：接 \([0,2]\)；\([2,3]\) 的 \(2 > 2\) 不成立，跳過；接 \([3,4]\)；\([1,5]\) 跳過；\([4,6]\) 的 \(4 > 4\) 不成立，跳過——答案 \(2\)。範例 2 是 \(k = 2\)，這份程式印 3、少了兩筆是正常的，子題組 1、2 的 \(40\) 分穩穩到手。

從 40 分到 100 分：接在「結束得最晚、但還接得上」的那台機器

機器變成 \(k\) 台，申請還是依結束時間排好、一筆一筆看。對目前這筆 \([L, R]\)，一台機器接得上的條件是「它上一筆的結束時間 \(< L\)」。接得上的機器可能不只一台，要接在結束時間最晚的那台：結束得早的機器留著，之後開始時間更早的申請才有機器可用。圖 1 走一遍範例 2——第 5 筆 \([5,6]\) 兩台都接得上，選了在 \(4\) 結束的 B，把在 \(3\) 結束的 A 留下來，第 7 筆 \([4,7]\) 才接得到；反過來先拿 A，\([4,7]\) 就沒有機器了，總數從 \(5\) 掉到 \(4\)。

沒有任何機器接得上就拒絕這筆：它結束得比後面每一筆都早，硬把某台機器上正在跑的那筆換掉（那筆結束時間 \(\le R\)）也換不出更多筆數。

程式上用 multiset<int> 存 \(k\) 台機器的結束時間，一開始放 \(k\) 個 \(-1\)（還沒用過）。對每筆申請，lower_bound(L) 指到第一台「結束時間 \(\ge L\)」的機器，它前面那一台就是「結束時間 \(< L\) 當中最晚的」；指到最前面代表沒有機器接得上。接了就把那台的結束時間刪掉、放進 \(R\)。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> l(n), r(n);
    for (int &v : l) cin >> v;
    for (int &v : r) cin >> v;

    vector<pair<int, int>> job(n);               // (結束時間, 開始時間)
    for (int i = 0; i < n; i++) job[i] = {r[i], l[i]};
    sort(job.begin(), job.end());

    multiset<int> busyUntil;                     // 每台機器上一筆申請的結束時間
    for (int i = 0; i < k; i++) busyUntil.insert(-1);   // 還沒用過＝在 -1 結束

    int count = 0;
    for (int i = 0; i < n; i++) {
        int start = job[i].second, finish = job[i].first;
        auto it = busyUntil.lower_bound(start);  // 第一台「結束時間 >= start」的機器：接不了
        if (it == busyUntil.begin()) continue;   // 沒有任何機器在 start 之前結束：這筆不接
        --it;                                    // 往前一格：結束時間 < start 當中最晚的那台
        busyUntil.erase(it);                     // 只刪這一台（傳 iterator，不是傳值）
        busyUntil.insert(finish);
        count++;
    }
    cout << count << '\n';
    return 0;
}

排序 \(O(n \log n)\)，每筆申請在 multiset 裡找、刪、放各 \(O(\log k)\)，\(n = 10^5\) 本站實測 \(0.06\) 秒。erase 一定要傳 iterator：傳值會把所有同值的機器一起刪掉，一開始 \(k\) 台都是 \(-1\)，第一筆申請就把全部機器刪光。

站上 CSES 中文題庫的 Movie Festival II 是同一題，只差那題前一場結束的時刻可以直接開始下一場（條件差一個等號），練完這題可以順手拿下。

測過再交：範例沒有「機器還沒用滿」的陷阱

三個範例蓋到了端點相碰（範例 3）與「要留下早結束的機器」（範例 2）。沒蓋到：只有一筆、開始等於結束、機器比申請多、時間頂到 \(10^8\)，以及兩種三個範例全過的錯法——依開始時間排序、機器還沒用滿就開新的一台。

六筆都親眼看過正確，這題就穩了。