题意：n个建筑，每个都需要修复，需要$t_i$的时间
若在$w_i$时之前还没修好，则GG
问最多能修几个
按GG时间排序
设当前建筑为i
若i能修，就修了
若不能修，在堆(维护$t_i$最大值)中找到之前最大的$t_j$
若$t_j>t_i$那么很显然修当前的更优，就进行反悔操作
不修j了，修i
#include<cstdio>#include<iostream>#include<cstring>#include<cctype>#include<queue>#include<algorithm>using namespace std;#define int long long#define olinr return#define _ 0#define love_nmr 0#define DB doublepriority_queue<int> q;inline int read(){ ???int x=0,f=1; ???char ch=getchar(); ???while(!isdigit(ch)) ???{ ???????if(ch==‘-‘) ???????????f=-f; ???????ch=getchar(); ???} ???while(isdigit(ch)) ???{ ???????x=(x<<1)+(x<<3)+(ch^48); ???????ch=getchar(); ???} ???return x*f;}inline void put(int x){ ???if(x<0) ???{ ???????x=-x; ???????putchar(‘-‘); ???} ???if(x>9) ???????put(x/10); ???putchar(x%10+‘0‘);}int n;struct node{ ???int t1; ???int t2; ???friend bool operator < (const node &a,const node &b) ???{ ???????return a.t2<b.t2; ???}}a[155050];int ans;signed main(){ ???n=read(); ???for(int i=1;i<=n;i++) ???{ ???????a[i].t1=read(); ???????a[i].t2=read(); ???} ???sort(a+1,a+n+1); ???int t=0; ???q.push(0); ???for(int i=1;i<=n;i++) ???{ ???????if(t+a[i].t1>a[i].t2) ???????{ ???????????if(a[i].t1<q.top()) ???????????{ ???????????????t-=q.top(); ???????????????q.pop(); ???????????????q.push(a[i].t1); ???????????????t+=a[i].t1; ???????????} ???????} ???????else ???????{ ???????????q.push(a[i].t1); ???????????ans++; ???????????t+=a[i].t1; ???????} ???} ???put(ans); ???olinr ~~(0^_^0)+love_nmr;}P4053 [JSOI2007]建筑抢修
原文地址：https://www.cnblogs.com/olinr/p/9574620.html