题目链接:https://ac.nowcoder.com/acm/problem/20154
思路:
首先将每栋建筑按照截至时间排序,当然你可以用结构体排序,或者定义二维数组,二位向量啥的,但是在这里,用pair会比较简单,pair 默认对first升序(若相等,对second 升序),这样可以避免写cmp函数或者重载运算符<。
但是要注意把截止时间放在first 把花费时间放在second
接着呢 我们把从截止时间早的开始 把凡是能修的就修,
能修指 now(现在的时间点)+修理所需要的时间<=截止时间
然后我们把修理时间放到一个优先队列(大根堆)里面
这样队列里面放的就都是我们修过的建筑的修理时间了
但是这样很难是最优解,我们很快就会遇到不能修的建筑了(即now(现在的时间点)+修理所需要的时间>截止时间)
这时候我们只要拿他和我们队列中的建筑比较,如果这个建筑的修理时间比我们之前已经修过的建筑要短,那就说明修这个建筑会比修之前的建筑更值得,所以我们就去掉之前建筑中的一个建筑了,换成修现在这个修理时间更短的建筑。
(再对这个更优解释一下,我们的数组是排过序的在后面的建筑是截止时间更晚的,如果这是后这个建筑的修理时间更短,那肯定换修他方案会更优。
举例:如果两个建筑a和b只能修一个,a截止时间晚修理时间短,那你肯定修a啊)
依照这种方式,遍历完n个建筑,就能得到最优解。
细节和详情看代码和注释,写的挺清楚的了。

#include<iostream>
#include<algorithm>
#include<queue>
#include<string>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<stack>
#include<set>
#include<map>
#define ll long long
using namespace std;
#define close_stdin  ios::sync_with_stdio(false)
int n;
const int maxn = 150007;
pair<ll,ll> a[maxn]; 
priority_queue<int> q; //放修理的楼的 修理时间
void my_input() { //输入数据
    cin >> n;
    for (int i = 1;i <= n;i++) { cin >> a[i].second >> a[i].first; }// 由于是要对 截止时间排序,所以把截至时间放在前面(first)
}
void solve() {
    sort(a + 1, a + 1 + n);
    ll now = 0; //表示当下的时间 ,由于T1 ,T2 的限制 所以必须用 longlong
    int cnt = 0;
    for (int i = 1;i <= n;i++) { //注意first是截止时间 second 是修理需要时间
        if (now + a[i].second <= a[i].first) {  //能修就先修着,后续再去调整
            cnt++;
            now += a[i].second;
            q.push(a[i].second);  //能修就把它放到q里面
        }
        else if (a[i].second< q.top()) { //由于前面能修就修,所以不是最优,一定会发生到i的时候修不了了,这时候进行优化
            now -= q.top(); //这时候 a[i] 的截止时间在 q.top对应的建筑后面而修理时间却比q.top短 所以很明显能修a[i] 并且修a【i】会更合理
            now += a[i].second;
            q.pop();
            q.push(a[i].second);        //这边只是将修的建筑一换一 来调高性价比 ,所以cnt不需要++
        }
    }
    cout << cnt;
}
int main() {
    close_stdin;//只是为了让cin和printf一样快
    my_input();
    solve();
}

谢谢浏览哈!