【每日一题】建筑抢修

题意

栋建筑，第 栋建筑需要 时间修，截止到 时间，问最多可以修多少建筑。

solution

我们可以类比成写作业，先截止的我们会先做，这是大体的贪心策略。但他并不是最优的，因为可能那一科会花你非常多的时间，够你做更多的科目，得不偿失。因此我们用优先队列维护做过的作业中花费时间最大的那份，当目前要做的作业时间不够的时候，与这个最大值比较看是否花的时间更少，可行的话就把这个塞进去，那个丢出来，这样做了同样多的作业却花了更少的时间，同时维护答案。

Code

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N = 5e5 + 5;
int n, sum, res;
pair<int, int> p[N];
priority_queue<int> q;
int main() {
  cin >> n;
  for (int i = 0; i < n; i++) cin >> p[i].y >> p[i].x;
  sort(p, p + n);
  for (int i = 0; i < n; i++) {
    if (sum + p[i].y <= p[i].x) {
      sum += p[i].y;
      res++;
      q.push(p[i].y);
    } else if (p[i].y < q.top()) {
      sum -= q.top();
      q.pop();
      q.push(p[i].y);
      sum += p[i].y;
    }
  }
  cout << res << '\n';
  return 0;
}