切割費用 題解｜APCS 2021 年 1 月中高級 第 3 題

前置知識

這題的核心推導（一刀的費用只跟左右最近的切點有關）下面會從頭講；要先會的是兩個工具，同一個主題兩邊都有的，對照著讀會更快上手：

• set：NTUCPC Guide〈Set 與 Map〉——set 裡的元素永遠排好序，insert 一個數是 \(O(\log n)\)；lower_bound(x) 給你「第一個 \(\ge x\) 的元素」的 iterator，往前退一格就是「最後一個 \(< x\) 的元素」。
• 鏈結串列（最後的「另一種做法」會用到）：NTUCPC Guide〈Linked List〉；吳邦一《AP325》第 3 章「串列鏈結」一節（教材 PDF 第 102～104 頁；Python 版第 3 章）——要帶走的是「用兩個陣列 prv[]、nxt[] 記每個元素的前後是誰，拿掉一個元素只要改兩個值」。

簡潔題意

一根棍子放在數線的 \([0, L]\) 上，依序切 \(n\) 刀，第 \(i\) 刀切在位置 \(x_i\)（位置互不相同、都在 \(0\) 和 \(L\) 之間）。切一刀的費用＝這個位置當時所在那一段的長度，求 \(n\) 刀的總費用。輸入每行給的是「位置 \(x\) 是第 \(i\) 刀」，行的順序不是切割順序（\(1 \le n \le 2 \times 10^5\)，\(1 \le L \le 10^7\)）。

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

• 子題組 1（\(20\) 分）：\(n \le 1000\)。
• 子題組 2（\(30\) 分）：\(n \le 50000\)。
• 子題組 3（\(50\) 分）：無額外限制。

先把輸入排回切割順序

輸入每行是「\(x\) 是第 \(i\) 刀」，開一個陣列 pos，讀到 x i 就寫 pos[i] = x——讀完之後 pos[1]、pos[2]、……就是第 \(1\) 刀、第 \(2\) 刀、……切在哪裡（題目講「第幾刀」，陣列從 \(1\) 用起，見語法書 6.3）。範例的三行是「\(2\) 是第 \(2\) 刀、\(3\) 是第 \(1\) 刀、\(5\) 是第 \(3\) 刀」，排回來的切割順序是 \(3, 2, 5\)。

一刀的費用：左右最近的切點

切第 \(i\) 刀時，棍子已經被前面 \(i - 1\) 刀切成好幾段，\(x_i\) 所在的那一段，左端是「前面的切點裡最靠近 \(x_i\) 的左邊那個」（沒有就是 \(0\)）、右端是「最靠近的右邊那個」（沒有就是 \(L\)），費用就是右端減左端。範例（圖 1）：第 \(1\) 刀切 \(3\)，還沒有任何切點，整根 \([0, 7]\)，費用 \(7\)；第 \(2\) 刀切 \(2\)，左邊最近是 \(0\)、右邊最近是 \(3\)，費用 \(3\)；第 \(3\) 刀切 \(5\)，左邊最近是 \(3\)、右邊最近是 \(7\)，費用 \(4\)。總共 \(7 + 3 + 4 = 14\)。

先拿下 20 分：每一刀掃一遍前面的切點

把「左邊最近」「右邊最近」直接照字面找：掃過前面每一刀，比 \(x_i\) 小的裡面取最大、比 \(x_i\) 大的裡面取最小（擂台法，初值用兩端 \(0\) 和 \(L\)）。

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

const int MAX_N = 200000;
long long pos[MAX_N + 1];        // pos[i] = 第 i 刀切在哪裡

int main() {
    int n;
    long long L;
    cin >> n >> L;
    for (int k = 0; k < n; k++) {
        long long x;
        int i;
        cin >> x >> i;
        pos[i] = x;                  // 先照「第幾刀」排回切割順序
    }
    long long total = 0;
    for (int i = 1; i <= n; i++) {
        long long left = 0, right = L;           // 先假設這段就是整根棍子
        for (int j = 1; j < i; j++) {            // 掃過前面每一刀，找最近的左右切點
            if (pos[j] < pos[i] && pos[j] > left) left = pos[j];
            if (pos[j] > pos[i] && pos[j] < right) right = pos[j];
        }
        total += right - left;
    }
    cout << total << endl;
    return 0;
}

每一刀掃過前面所有切點，總共 \(0 + 1 + \cdots + (n - 1) \approx n^2 / 2\) 次比較：\(n = 1000\) 時 \(5 \times 10^5\) 次、一瞬間；\(n = 5 \times 10^4\) 時 \(1.25 \times 10^9\) 次，本站實測 \(0.8\) 到 \(2.8\) 秒，時限 \(1\) 秒，子題組 2 拿不穩；\(n = 2 \times 10^5\) 要 \(48\) 秒。子題組 1 的 \(20\) 分穩穩到手。

總費用要用 long long：每一刀的費用不超過 \(L\)，\(n\) 刀最多 \(n \times L = 2 \times 10^5 \times 10^7 = 2 \times 10^{12}\)，超過 int 的 \(2147483647\)（估算方法見語法書 2.9）。

從 20 分到 100 分：讓「找最近的切點」變快

慢的地方只有一個：找 \(x_i\) 左右最近的切點要掃過所有切點。把切點放進 set——它永遠保持排好序，lower_bound(x) 直接給「第一個 \(\ge x\) 的切點」，往前退一格就是「最後一個 \(< x\) 的切點」，兩個都是 \(O(\log n)\)。一開始先把 \(0\) 和 \(L\) 放進去，這樣永遠找得到左右鄰居，不用特判「左邊沒有切點」。

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

const int MAX_N = 200000;
long long pos[MAX_N + 1];        // pos[i] = 第 i 刀切在哪裡

int main() {
    int n;
    long long L;
    cin >> n >> L;
    for (int k = 0; k < n; k++) {
        long long x;
        int i;
        cin >> x >> i;
        pos[i] = x;                  // 先照「第幾刀」排回切割順序
    }
    set<long long> cuts;             // 目前已有的切點，一開始只有兩端
    cuts.insert(0);
    cuts.insert(L);
    long long total = 0;
    for (int i = 1; i <= n; i++) {
        auto right = cuts.lower_bound(pos[i]);   // 第一個 >= pos[i] 的切點：右鄰居
        auto left = right;
        left--;                                  // 它的前一個：左鄰居
        total += *right - *left;                 // 這一刀切的是 [左鄰居, 右鄰居] 這段
        cuts.insert(pos[i]);
    }
    cout << total << endl;
    return 0;
}

每一刀一次 lower_bound、一次 insert，\(O(n \log n)\)，\(n = 2 \times 10^5\) 本站實測 \(0.2\) 秒。left-- 之前 right 一定不是 begin()：題目保證 \(0 < x_i < L\)，set 裡的 \(0\) 永遠排在 \(x_i\) 前面、\(L\) 永遠排在後面，所以兩個鄰居都找得到。

測過再交：範例只有三刀

範例的三刀是「中間、左、右」各一刀，輸入順序也剛好跟切割順序不同；沒蓋到的是：只有一刀、同樣的位置換個順序切、兩刀都貼著邊、以及最大的 \(n\)（驗 long long 和速度）。

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

另一種做法：倒著撤銷

正著做要「動態」找鄰居；反過來想就不用：先把所有切點排好序，直接得到全部切完的樣子——每個切點的左右鄰居一目瞭然。然後從最後一刀往回撤銷：撤銷第 \(i\) 刀，就是把切點 \(x_i\) 拿掉、左右兩段黏回去；因為比它晚的刀都已經撤銷了，黏回去的那一段正好就是第 \(i\) 刀當初切的那一段，長度就是它的費用（圖 2）。

「拿掉一個切點、左右接起來」用鏈結串列是 \(O(1)\)：prv[k]、nxt[k] 記排序後第 \(k\) 個切點的前後是誰，拿掉 \(k\) 就是 nxt[prv[k]] = nxt[k]、prv[nxt[k]] = prv[k]。排序時把「第幾刀」一起帶著（用 pair），才知道第 \(i\) 刀排序後在第幾個。整題只剩排序的 \(O(n \log n)\)，本站實測 \(0.1\) 秒。

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

const int MAX_N = 200000;
long long pos[MAX_N + 2];        // 排好序的座標：pos[0] = 0、pos[n + 1] = L
int order[MAX_N + 1];            // order[i] = 第 i 刀的切點排序後是第幾個
int prv[MAX_N + 2], nxt[MAX_N + 2];

int main() {
    int n;
    long long L;
    cin >> n >> L;
    vector<pair<long long, int>> cuts;       // (座標, 第幾刀)
    for (int k = 0; k < n; k++) {
        long long x;
        int i;
        cin >> x >> i;
        cuts.push_back({x, i});
    }
    sort(cuts.begin(), cuts.end());
    pos[0] = 0;
    pos[n + 1] = L;
    for (int k = 0; k < n; k++) {
        pos[k + 1] = cuts[k].first;
        order[cuts[k].second] = k + 1;
    }
    for (int k = 0; k <= n + 1; k++) {       // 全部切完的樣子：每個切點的左右鄰居
        prv[k] = k - 1;
        nxt[k] = k + 1;
    }
    long long total = 0;
    for (int i = n; i >= 1; i--) {           // 從最後一刀往回撤銷
        int k = order[i];
        total += pos[nxt[k]] - pos[prv[k]];  // 黏回去的那一段，就是當初這一刀切的那段
        nxt[prv[k]] = nxt[k];                // 把切點 k 從串列中拿掉
        prv[nxt[k]] = prv[k];
    }
    cout << total << endl;
    return 0;
}

兩種做法都是滿分；set 版照題意正著走、程式短，倒著撤銷是很多題都用得上的思路（「刪除很難、加入很簡單」的問題，倒過來做就只剩加入）。