题面

有\(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;
}

Luogu P4053 [JSOI2007]建筑抢修

原文：https://www.cnblogs.com/wsfwsf/p/13915827.html