CSES – Traffic Lights

題目連結

題意

有一個長度 x 的街道，一開始都沒有紅綠燈。現在我們要依序加入 n 個紅綠燈。每次加完一個紅綠燈，輸出道路中最長的一段都沒有紅綠燈的長度。

解題想法

這題我們要開兩個 set / multiset 來維護。一個是維護現在有的紅綠燈 s，另一個用來維護紅綠燈之間的距離 dis。
每次加入一個新的紅綠燈時，先找到那個位置左右的紅綠燈是誰，把他們的距離從 dis 中移除，換上新的距離
(有一個新的在中間)。操作完再把新的燈也加入 s 就好。每次輸出答案就是輸出 dis 中的最後一個數字 (最大)。

小技巧: 可以先將 0, x 都放到路燈中，當作邊界，這樣可以比較輕鬆計算距離!

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int x, n;
    cin >> x >> n;
    set <int> s; // 紀錄路燈
    s.insert(0); // 邊界
    s.insert(x);
    multiset <int> dis; // 紀錄距離
    dis.insert(x);
    for(int i = 0;i < n;i++){
        int p;
        cin >> p;
        auto it1 = s.upper_bound(p); // 找到右邊第一個 (第一個比他位置大)
        auto it2 = it1; // 左邊第一個 (前一個)
        --it2;
        dis.erase(dis.find(*it1-*it2)); // 移除原本的
        dis.insert(p-*it2); // 加入新的距離
        dis.insert(*it1-p);
        s.insert(p); // 加入新的燈
        cout << *--dis.end() << " \n"[i == n-1]; // 輸出最大的距離
    }
}