建筑抢修

一开始纠结是该按照所需时间长短排序还是截止时间 其实很简单 如果建筑截止时间很长 但是所需时间很短 我肯定是越晚做越优 这样可以腾出跟多的时间去做截止时间短的建筑 那么就根据建筑的截止时间从小到大依次排序 依次去抢修这些建筑 如果累加时间加上当前的建筑所需时间小于等于当前建筑截止时间 那么我就把这个所需时间压入优先队列中(大根堆) 如果大于当前建筑截止时间 那么我就对比该建筑所需时间与堆的顶端存储的所需时间对比 如果该建筑所需时间更短 那么我就把顶端弹出 将这个时间推入(此处为贪心) 最后堆内存下的所有时间即为能抢修最多建筑时的抢修建筑方案

#include <bits/stdc++.h>
using namespace std;
using pi = pair<int, int>;

int main () {
  ios::sync_with_stdio(0), cin.tie(0);
  int n;cin >> n;
  vector<pi> a(n);
  for (int i = 0;i < n; ++ i) cin >> a[i].first >> a[i].second;
  sort(a.begin(), a.end(), [](const pi &u, pi &v) {
    return u.second < v.second;
  });
  priority_queue<int> pq;
  int t = 0;
  for (int i = 0;i < n; ++ i) {
    if (a[i].first + t <= a[i].second) {
      pq.push(a[i].first);
      t += a[i].first;
    }
    else{
      if (a[i].first < pq.top()) {
        t -= pq.top();
        pq.pop();
        pq.push(a[i].first);
        t += a[i].first;
      }
    }
  }
  cout << pq.size() << '\n';
}