TIOJ 1337：隕石

TIOJ 1337：隕石

題目大意：有 $N$ 顆隕石即將墜落在 $\text{CK}$ 市了！！！！！
$\text{CK}$ 市是一條直線。因為 $\text{CK}$ 市相當地廣大，在這題我們暫時假設 $\text{CK}$ 市沒有盡頭。

$\text{CK}$ 市的科學家合力估算了 $N$ 顆隕石墜落的地點。根據計算，第 $i$ 顆隕石墜落後將破壞區間 $[L_i, R_i)$ 的 $\text{CK}$ 市。也就是說所有座標大於等於 $L_i$ 並小於 $R_i$ 的地方都會被破壞殆盡。為了防止世界被破壞，$\text{CK}$ 市的市長祭出了兩個手段。

第一個手段是築起防護罩。每層防護罩都可以籠罩整個 $\text{CK}$ 市。然而如果座標 $x$ 處受到隕石衝擊，那麼該處的防護罩就會減少一層。不過 $\text{CK}$ 市的防護罩材料特別：一處的結構受損並不會影響到其它地方的結構穩定度。當然，可以築起多層防護罩提供更多的防護。
第二個手段是消滅隕石。然而尤於填充能量費時，在大災難來臨之前，$\text{CK}$ 市只來得及射下 $K$ 顆隕石。

雖然當然也可以直接建造 $N$ 層防護罩，但是建造愈多防護罩意味著愈多的損失。請問在最佳策略下，$\text{CK}$ 市能建造最少幾層的防護罩讓所有 $\text{CK}$ 市內的地區安然無恙？

解法：使用二分搜判斷建 $(l + r) / 2$ 層能不能擋下所有隕石，如果可以，把 $r$ 設為 $(l + r) / 2$，否則將 $l$ 設成  $(l + r) / 2 + 1$。

$\text{Code：}$

#pragma GCC optimize("O3")
#include <iostream>
#include <set>
using namespace std;

#define F first
#define S second

int n, k;
multiset<pair<int, int> > ms;

bool ok (int x) {
    int step = k;
    multiset<pair<int, int> > rev;
    for (auto p = ms.begin(); p != ms.end(); p++) {
        int l = p->F, r = p->S;
        while (!rev.empty() && rev.begin()->F <= l)
            rev.erase (rev.begin());
        rev.insert ({r, l});
        if (rev.size() > x) {
            if (step == 0)
                return 0;
            rev.erase (--rev.end());
            step--;
        }
    }
    return 1;
}

void solve() {
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        ms.insert ({a, b});
    }

    int l = 0, r = n - k;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (ok (mid))
            r = mid;
        else
            l = mid + 1;
    }
    cout << l << '\n';
}

int main() {
    ios::sync_with_stdio (false), cin.tie (0);
    solve();
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！