[TIOJ]1337. 隕石

題目連結：http://tioj.ck.tp.edu.tw/problems/1337

因為答案具有單調性，所以可以對答案二分搜。
驗證答案的時候可以從左掃過去，如果這一點的隕石數量大於當前防護罩數量的話就需要把隕石打掉，打掉右界最大值的那一顆隕石會是最佳解（用priority_queue維護），最後檢查隕石數量有沒有大於上限即可。
因為數值範圍太大所以要離散化。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <bitset>
#include <queue>
#include <vector>
#define lld long long
#define PB push_back
#define F first
#define S second
#define jizz cin.tie(0);ios_base::sync_with_stdio(0);
#define endl '\n'
using namespace std;
typedef pair<int,int> Pair;
int n,k;
vector<int> v;
vector<Pair> l;
int b[200005];
bool check(int x){
    priority_queue<int, vector<int> , less<int> > pq;
    fill(b,b+200005,0);
    int p = 0,t = 0,m = k;
    for(int i = 0 ; i < v.size() ; i++){
        while(p < n && l[p].F == i)t++,b[l[p].S]++,pq.push(l[p].S),p++;
        if(b[i])t -= b[i];
        int tmp = t-x;
        if(tmp > 0){
            m -= tmp;
            t -= tmp;
            while(tmp--){
                b[pq.top()]--;
                pq.pop();
            }
            if(m < 0)return 0;
        }
    
    }
    return 1;
}
int main(){jizz
    cin >> n >> k;
    for(int i = 0 ; i < n ; i++){
        int a, b; cin>>a>>b;
        l.PB({a,b});
        v.PB(a); v.PB(b);
    }
    sort(v.begin(), v.end());
    sort(l.begin(), l.end());
    v.resize(unique(v.begin(), v.end())-v.begin());
    for(int i = 0 ; i < n ; i++){
        l[i].F = lower_bound(v.begin(),v.end(),l[i].F)-v.begin();
        l[i].S = lower_bound(v.begin(),v.end(),l[i].S)-v.begin();
    }
    int L = -1,R = n;
    while(R - L > 1){
        int M = (L+R)/2;
        if(check(M))R = M;
        else L = M;
    }
    cout << R << endl;
    return 0;
}