题面
有\(N\)个建筑需要修理,修理第\(i\)个建筑需要在\(a_i\)前花时间\(t_i\)
问:最多可以修理多少建筑
分析
显然,需要按\(a_{i}\)排序,之后考虑可回溯型贪心
对于一个建筑,如果在结尾时间能修就修,否则加入堆中并删去修理时间最长的
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+5;
int n;
struct A{int a,b; }a[N];
bool cmp(A i,A j) {
return i.b<j.b;
}
priority_queue<int>q;
int main() {
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d%d",&a[i].a,&a[i].b);
}
sort(a+1,a+n+1,cmp);
ll sum=0;
for(int i=1;i<=n;i++) {
sum+=a[i].a; q.push(a[i].a);
if(sum>a[i].b) {
sum-=q.top(); q.pop();
}
}
printf("%d\n",(int)q.size());
return 0;
}