圓環出口 題解｜APCS 2020 年 7 月中高級 第 3 題

前置知識

這題的推導（怎麼把「走到哪裡會達標」變成一次查詢）下面會從頭講；要先會的是兩個工具，同一個主題兩邊都有的，對照著讀會更快上手：

• 前綴和：NTUCPC Guide〈前綴和與差分〉——pre[i] 存「前 \(i\) 個數的總和」，任何一段連續的總和都是兩個 pre 相減，一次 \(O(1)\)。
• 二分搜與 lower_bound：NTUCPC Guide〈搜尋〉——在遞增的陣列裡找「第一個 \(\ge x\) 的位置」只要 \(O(\log n)\)；lower_bound(起點, 終點, x) 直接回傳那個位置的指標，減掉陣列開頭就是索引。
• 吳邦一《AP325》第 2 章的例題 P-2-15 就是這一題（教材 PDF 第 79～81 頁；Python 版第 2 章），裡面示範了「環」的兩種處理方式：超過尾端就從頭接著算，或者把陣列照抄一份接在後面——下面用的是第二種。

簡潔題意

\(n\) 個房間圍成一圈，編號 \(0\) 到 \(n - 1\)，只能往編號加一的方向走，\(n - 1\) 的下一間是 \(0\)。進入房間 \(i\) 拿 \(p_i\) 點，一開始待的那間也算。依序有 \(m\) 個任務，第 \(k\) 個任務要蒐集 \(q_k\) 點：從目前的房間開始累積，走到某間 \(t\) 時累積到 \(\ge q_k\) 就算完成，然後停在 \((t + 1) \bmod n\)，下一個任務從那裡重新累積。一開始在房間 \(0\)，問做完 \(m\) 個任務後停在哪一間（\(1 \le n \le 2 \times 10^5\)，\(1 \le m \le 2 \times 10^4\)，\(p\) 的總和不超過 \(10^9\)，每個 \(q_k\) 不超過 \(p\) 的總和）。

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

• 子題組 1（\(20\) 分）：\(n, m \le 100\)。
• 子題組 2（\(80\) 分）：無額外限制。

先拿下 20 分：一間一間走

照題意模擬：目前在 \(s\)，先把 \(s\) 的點數算進去（出發那間也算），不夠就往下一間走、把點數加上，直到累積 \(\ge q\)；達標的那間是 \(t\)，下一個任務從 \((t + 1) \bmod n\) 開始。

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

const int MAX_N = 200000;
long long p[MAX_N];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> p[i];
    int s = 0;                               // 目前站在哪一間
    for (int k = 0; k < m; k++) {
        long long q;
        cin >> q;
        long long got = p[s];                // 出發那間也算點數
        int t = s;
        while (got < q) {                    // 不夠就往下一間走
            t = (t + 1) % n;
            got += p[t];
        }
        s = (t + 1) % n;                     // 達標那間的下一間
    }
    cout << s << endl;
    return 0;
}

題目保證 \(q\) 不超過所有 \(p\) 的總和，所以每個任務最多走一整圈（\(n\) 間）就一定達標，不會無窮迴圈。\(m\) 個任務最多走 \(n \times m\) 間：子題組 1 是 \(10^4\)，一瞬間；子題組 2 是 \(2 \times 10^5 \times 2 \times 10^4 = 4 \times 10^9\)，\(q\) 大的測資本站實測 \(7\) 到 \(14\) 秒，時限 \(1\) 秒。子題組 1 的 \(20\) 分穩穩到手。

從 20 分到 100 分：前綴和＋二分搜

慢的地方只有一個：每個任務「一間一間加」。換個方式問同一件事——從 \(s\) 出發，走到第幾間時累積的點數第一次 \(\ge q\)？這正是前綴和加二分搜最擅長的問題。

把環展開成兩圈：展開後編號 \(0\) 到 \(2n - 1\)，第 \(i\) 格的點數是 \(p_{i \bmod n}\)（第二圈照抄第一圈）。令 pre[i] 是展開後前 \(i\) 格的總和（pre[0] = 0）。從 \(s\) 走到第 \(t\) 格（含兩端）拿到的點數就是 pre[t + 1] - pre[s]。要找最小的 \(t\) 使它 \(\ge q\)，等價於找第一個 \(\ge\) pre[s] + q 的 pre[j]（\(j = t + 1\)）。因為每個 \(p_i \ge 1\)，pre 嚴格遞增，直接 lower_bound 從 pre + s + 1 找起；找到的 \(j\) 就是 \(t + 1\)，正好是「達標那間的下一間」，取 \(j \bmod n\) 得到真正的房間編號（圖 1）。

為什麼展開兩圈就夠：\(q\) 不超過總和，所以從 \(s\) 出發最多走 \(n\) 格就達標，\(t \le s + n - 1\)、\(j \le s + n \le 2n - 1\)，永遠落在展開後的範圍裡，lower_bound 一定找得到。

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

const int MAX_N = 200000;
long long p[MAX_N];
long long pre[2 * MAX_N + 1];        // pre[i] = 展開成兩圈後，前 i 間房間的點數總和

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> p[i];
    for (int i = 0; i < 2 * n; i++) pre[i + 1] = pre[i] + p[i % n];   // 第二圈照抄第一圈
    int s = 0;                                       // 目前站在哪一間
    for (int k = 0; k < m; k++) {
        long long q;
        cin >> q;
        // 從 s 走到第 t 間（展開後的編號）拿到的點數是 pre[t + 1] - pre[s]，
        // 要找最小的 t 使它 >= q，也就是第一個 >= pre[s] + q 的 pre[j]，j = t + 1
        int j = lower_bound(pre + s + 1, pre + 2 * n + 1, pre[s] + q) - pre;
        s = j % n;                                   // j = t + 1 正好就是「達標那間的下一間」
    }
    cout << s << endl;
    return 0;
}

每個任務一次 lower_bound，整題 \(O(n + m \log n)\)，最大測資本站實測 \(0.05\) 秒。

兩圈的總和最多 \(2 \times 10^9\)，比 int 的上限 \(2147483647\) 小（估算方法見語法書 2.9），所以 pre 用 int 其實裝得下，本站實測也全過；但只差 \(7\%\)，用 long long 零成本，不用賭。

測過再交：範例沒有「剛好走滿一圈」

兩個範例的任務都停在圈子中間；沒蓋到的是：只有一間房、\(q\) 恰好等於總和（要走滿一整圈回到原地）、\(q\) 恰好等於出發那間的點數（出發那間要算）、任務跨過 \(n - 1\) 回到 \(0\)，以及最大的 \(n\)、\(m\)（驗速度）。

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