[TIOJ] 1337. 隕石

題目連結:http://tioj.infor.org/problems/1337

---

本題一樣也是校內補選題，當時在寫的時候我一值莫名其妙唬爛到60分，學長一直rejudge掉我，但我又有其他騙分的方式，所以最後就因為這題我上機變第一www，不過說實在那時寫的是假解，實在不太好
正題：本題雖然可以轉成區間最大值，然後用個線段樹可以應付沒有炸彈的情況，但是若用線段樹很難維護要炸掉誰，所以不妨對答案二分搜，驗證那個答案可不可能的方式就是從左掃到右，發現疊起來值太大時就把右界最遠的線段pop掉，因為他一定後面還會影響到很多人，掃過去看要炸的數量是不是比炸彈多，過多就表示不可能，反之就有可能。不過要特別注意一下，二分搜時上界記得設成n-k，免得不小心因為常數TLE掉。複雜度$O(n log^2 n)$

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

#define FF first
#define SS second

int n,k;

struct block{
    vector<int> end;
    int val;
};

map<int,block> mm;

inline bool test(int);

int main(){
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++){
        int l,r;
        scanf("%d%d",&l,&r);
        mm[l].end.push_back(r);
        mm[l].val++;
        mm[r].val--;
    }
    int uBound=n-k, lBound=-1;
    while(uBound-lBound!=1){
        bool qq = test((uBound+lBound)/2);
        if(qq) uBound=(uBound+lBound)/2;
        else lBound=(uBound+lBound)/2;
    }
    printf("%d",uBound);
    return 0;
}

inline bool test(int x){
    int bomb = k;
    priority_queue<int> pq;
    unordered_map<int,int> oao;
    auto i = mm.begin();
    int last=0;
    while(i!=mm.end()){
        int cVal = i->SS.val;
        for(auto j : i->SS.end)
            pq.push(j);
        if(oao.find(i->FF)!=oao.end())
            cVal += oao[i->FF];
        int cSum= last+cVal;
        while(cSum > x){
            int tt = pq.top();
            pq.pop();
            oao[tt]++;
            cSum--;
            bomb--;
        }
        last = cSum;
        if(bomb<0) return 0;
        i++;
    }
    return 1;
}