​ : 在什么时候建筑损坏

​ : 修复 所花时间

算法：贪心+堆维护

贪心策略：

直接按 贪心？显然不行。
那我们考虑先按 贪心，中途再更改。
按 从小到大排序之后，开始轮流遍历每个建筑。
如果中途某个建筑 无法在 ​ 的时间内修复，那么在先前选择修复的建筑中拿出 ​ 最大的 号建筑。若 ​，则放弃 转而修 。(主思路)

证明

显然是对的，感性理解即可

CODE

#include<bits/stdc++.h>
using namespace std;
#define I inline
#define ri register int
#define ll long long
#define For(i , x , y) for(ri i = x ; i <= y ; ++ i)
#define Next(i , u) for(ri i = head[u] ; i ; i = e[i].nxt)

I int read() {
    int s = 0 ,w = 1; char ch = getchar();
    while(ch < 48 || ch > 57) {if(ch == '-') w = -1; ch = getchar();}
    while(ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48) , ch = getchar();
    return s * w;
}
const int N = 2e5 + 5;

struct node {
    int T1 , T2 ;
} a[N];

int n , Ans;

I bool cmp (node A , node B) {
    return A.T2 < B.T2;
}

priority_queue <int> q;

signed main() {
    n = read();
    For(i , 1 , n) a[i].T1 = read() , a[i].T2 = read();
    sort(a + 1 , a + n + 1 , cmp);
    while(q.size()) q.pop();
    int now = 0;
    For(i , 1 , n) {
        if(now <= a[i].T2 - a[i].T1) now += a[i].T1 , ++ Ans , q.push(a[i].T1);
        else {
            int x = q.top() ; 
            if(x > a[i].T1 && !q.empty()) {
                q.pop() ; now = now - x + a[i].T1;
                q.push(a[i].T1);
            }
        }
    }    
    cout << Ans << endl;
    return 0;
}