这是我第一次做到反悔贪心的题目
座建筑有两个参数:需要秒维修以及需要在秒之前完成维修,否则报废
无论是按照从小到大排序或者从小到大排序都会有个问题,就是可以一开始就选择了很不好的选择,例如我按照从小到大排序,我的想法是物品维修时间小的先修,维修时间大的后修。
反例:
10 30
20 20
如果我先维修第一个,那么就不能维修第二个了;但是如果我先维修第二个,那么也可以继续维修第一个。

如何确定那个先修,那个后修呢?这与它们的紧张度。
在这道题目里面,由决定,所以我们需要按照从小到大排序。但是也会出现上面反例的情况,这时候就需要做出反悔了,我将之前一个耗时大的给删除掉,意思就是之前维修时间很大的一个建筑我反悔了,我不修了。那么我现在消耗的总时间就减少了,那么就更优的继续选择.

证明为什么是按照从小到大排序:
假设我先维修第座建筑可以,然后再维修第座建筑也可以:那么
假设我先维修第座建筑可以,然后再维修第座建筑也可以:那么
所以有:,所以
所以按照从小到大排序

定义表示我在维修过程中消耗的总时间,表示第座建筑需要维修的时间,a[i].second表示第座建筑需要在此之前完成维修。
  1. 如果,那么我直接就维修这个物品,所以
  2. 如果,那么如果之前存在一个建筑的维修时间比现在大,那么我是不是就可以将之前的这个建筑给删除掉,进而维修现在的,那么不变,因为之前的维修时间大于,那么既然将之前的一个建筑删了,那么现在的一定是可以维修的;并且总时间
但是如何找到之前已经维修的所有建筑里面维修时间最大的一个建筑呢?对,聪明的你已经想到了用来维护最大值!
完整的思路:
  1. 如果,那么我直接就维修这个物品,所以
  2. 如果,那么如果,那么
因为优先队列里面的元素表示的就所有已经维修的建筑的维修时间,所以最终就是答案,就多余了
总代码:
#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


bool cmp(pair<int, int> a, pair<int, int> b){
    return a.second < b.second;
}
signed main(){
    HelloWorld;
    
    int n; cin >> n;
    vector<pair<int, int> > a(n + 1);
    for(int i = 1; i <= n; i ++) cin >> a[i].first >> a[i].second;
    sort(a.begin() + 1, a.begin() + 1 + n, cmp);  
    
    priority_queue<int> q;
    int time = 0;
    for(int i = 1; i <= n; i ++){
        if(time + a[i].first <= a[i].second){
            time += a[i].first;
            q.push(a[i].first);
        }
        else if(q.size() && q.top() > a[i].first){
            time += a[i].first - q.top();
            q.pop();
            q.push(a[i].first);
        }
    }
    cout << q.size() << endl;
    return 0;
}`