帶著板凳排雞排的高人 題解｜APCS 2019 年 2 月高級 第 4 題

前置知識

這題是「往前找第一個比自己高的人」加上一個每人不同的門檻，下面的講解直接把這些當成已知，沒讀過的先讀；同一個主題兩邊都有的，對照著讀會更快上手：

• 單調堆疊（往左找第一個比自己高／矮的人）：吳邦一《AP325》第 3 章的 P-3-4「最接近的高人」就是本題沒有板凳的版本（教材 PDF 第 95～97 頁，含「為什麼不比自己高的人可以直接丟掉」與均攤分析），本題是它後面的習題 Q-3-5（PDF 第 98～99 頁）；NTUCPC Guide〈單調隊列〉的第一個例題「左邊第一個比較小的數」是同一件事的鏡像，要帶走的是「一個人什麼時候永遠不會再是答案」這種想法。
• 二分搜：NTUCPC Guide〈搜尋〉——在「前段都成立、後段都不成立」的序列上找交界。本題要在堆疊裡二分搜，不能只看最上面那個。
• vector 當堆疊用：push_back、pop_back、back() 就夠；用 vector 而不用 stack，是因為二分搜要用索引看裡面的每一個元素。

簡潔題意

\(n\) 個人排成一排，第 \(i\) 人身高 \(h_i\)、站上板凳後眼睛的高度是 \(h_i + p_i\)。他往前看，前方最近一個身高嚴格大於 \(h_i + p_i\) 的人會擋住視線（前面的人都站在地上，用自己的身高 \(h_j\) 來擋），他看得到自己和那個人之間的所有人；沒有人擋就看得到前面全部。求每個人看到的人數總和（\(1 \le n \le 2 \times 10^5\)，\(1 \le h_i \le 10^7\)，\(0 \le p_i \le 10^7\)）。（APCS 逐筆給分。）

先把題目翻成程式：對每個人往前找第一個夠高的人

第 \(i\) 人的門檻是 \(h_i + p_i\)。從第 \(i - 1\) 人開始往前走，碰到第一個 \(h_j > h_i + p_i\) 的人就停，他看到的人數是 \(i - j - 1\)；走到最前面都沒碰到，就看到 \(i - 1\) 個人。範例的門檻是 \(5, 4, 5, 1, 4\)：第 3 人門檻 \(5\)，前面身高 \(5\) 的第 1 人不嚴格大於 \(5\)，所以看得到 \(2\) 人；第 4 人門檻 \(1\)，往前碰到身高 \(4\) 的第 2 人停下，看到 \(1\) 人。

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

int main() {
    int n;
    cin >> n;
    vector<int> h(n + 1), p(n + 1);
    for (int i = 1; i <= n; i++) cin >> h[i];
    for (int i = 1; i <= n; i++) cin >> p[i];

    long long total = 0;
    for (int i = 1; i <= n; i++) {
        int limit = h[i] + p[i];
        int j = i - 1;                               // 從前一個人開始往前找
        while (j >= 1 && h[j] <= limit) j--;         // 不夠高就跳過；j 停在擋住視線的人，或 0
        total += i - j - 1;                          // j 與 i 之間的人數（j = 0 ＝ 沒人擋，看到 i - 1 個）
    }
    cout << total << '\n';
    return 0;
}

答案最大是每個人都看到前面全部：\(0 + 1 + \cdots + (n - 1) = n(n - 1) / 2\)，\(n = 2 \times 10^5\) 時是 \(19999900000\)，超過 int 的 \(2147483647\)（語法書 2.9），total 要用 long long。門檻 \(h_i + p_i\) 最多 \(2 \times 10^7\)，int 裝得下。

這份程式對小測資是對的，但 \(n = 2 \times 10^5\)、身高全相同、板凳全是 \(0\) 時，每個人都要一路走到最前面，總共走 \(n(n - 1) / 2 \approx 2 \times 10^{10}\) 步，本站實測 \(6.4\) 秒，超過 \(2\) 秒的時限。

滿分做法：候選名單只留「由高到矮」的人，再二分搜

往前找的時候，真的需要一個一個看嗎？假設第 \(j\) 人後面有一個不比他矮的第 \(k\) 人（\(j < k\)，\(h_k \ge h_j\)）。之後任何人往前看，一定先碰到第 \(k\) 人：如果第 \(k\) 人擋得住，答案是第 \(k\) 人或更近的人，輪不到第 \(j\) 人；如果第 \(k\) 人擋不住，第 \(j\) 人更矮，也擋不住。所以第 \(j\) 人永遠不會再是任何人的答案，可以從候選名單裡永久刪掉。

照這個規則維護名單：第 \(i\) 人處理完後，把名單尾端所有身高 \(\le h_i\) 的人刪掉，再把自己加到尾端。這樣名單裡的人由前到後身高嚴格遞減——每次只動尾端，用 vector 當堆疊剛好。每個人進名單一次、最多被刪一次，整理名單的總工作量是 \(O(n)\)。

沒有板凳的版本（AP325 的 P-3-4）到這裡就結束了：名單尾端第一個比 \(h_i\) 高的人就是答案，而且刪完之後尾端那個人就是他。有板凳就不行——門檻 \(h_i + p_i\) 可能比 \(h_i\) 高很多，答案可能在名單中間。但名單身高遞減，「身高 \(>\) 門檻」的人集中在前段，後段全部不夠高，用二分搜找前段的長度，前段最後一個人就是最近的擋人者；前段長度為 \(0\) 就是沒人擋。圖 1 走一遍範例：第 4 人門檻 \(1\)，名單 \([1(5), 2(4), 3(1)]\) 的前段是前兩個，所以被第 2 人擋住；第 5 人門檻 \(4\)，名單 \([1(5), 2(4), 4(1)]\) 只有第 1 人比 \(4\) 高，看到 \(3\) 人。

先查詢再整理名單：查的時候名單裡還沒有自己，不會把自己算進去；而且刪掉的是不比自己高的人，門檻 \(h_i + p_i \ge h_i\)，這些人本來就不可能擋住自己，先刪後查也對，但先查後刪比較不容易想錯。

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

int main() {
    int n;
    cin >> n;
    vector<int> h(n + 1), p(n + 1);
    for (int i = 1; i <= n; i++) cin >> h[i];
    for (int i = 1; i <= n; i++) cin >> p[i];

    vector<int> cand;                                // 候選人的編號：由前到後身高嚴格遞減
    long long total = 0;
    for (int i = 1; i <= n; i++) {
        int limit = h[i] + p[i];
        int lo = 0, hi = cand.size();                // 「身高 > limit」的候選人是前段，找前段長度
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (h[cand[mid]] > limit) lo = mid + 1;  // mid 還在前段：長度至少 mid + 1
            else hi = mid;                           // mid 不夠高：前段長度最多 mid
        }
        int blocker = (lo == 0) ? 0 : cand[lo - 1];  // 前段最後一個＝最近的擋人者；0 ＝ 沒人擋
        total += i - blocker - 1;
        while (!cand.empty() && h[cand.back()] <= h[i]) cand.pop_back();   // 不比 i 高的人以後沒用了
        cand.push_back(i);
    }
    cout << total << '\n';
    return 0;
}

每人一次二分搜 \(O(\log n)\)、整理名單均攤 \(O(1)\)，總共 \(O(n \log n)\)，剛才那筆 \(6.4\) 秒的測資本站實測 \(0.04\) 秒。

測過再交：範例沒有「等於門檻」與「超過 int」

範例蓋到了「板凳讓矮子看得遠」（第 3 人）與「門檻比自己身高低時被前面的人擋住」（第 4 人）。沒蓋到：身高剛好等於門檻、數值頂到 \(10^7\)、答案超過 int、以及一種範例會過的錯法——用門檻去踢名單裡的人。

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