看题目就想到 $dp$，想不出来就去想贪心...
考虑按右端点排序，一个个修，如果在修某个建筑 $i$ 时发现来不及了，说明前 $i$ 个建筑最多只能修 $i-1$ 个
那么我们把前 $i$ 个中耗时最长的那个放弃，这样省下的时间最多
然后用优先队列维护一下就行
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<queue> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=4e5+7; struct dat { int t,r; inline bool operator < (const dat &tmp) const { return r!=tmp.r ? r<tmp.r : t<tmp.t; } }d[N]; priority_queue <int> Q; int n,cnt; int main() { n=read(); for(int i=1;i<=n;i++) d[i].t=read(),d[i].r=read(); sort(d+1,d+n+1); int now=0; for(int i=1;i<=n;i++) { if(now+d[i].t<=d[i].r) { now+=d[i].t,cnt++,Q.push(d[i].t); continue; } if(Q.empty()||Q.top()<=d[i].t) continue; now-=Q.top(); now+=d[i].t; Q.pop(); Q.push(d[i].t); } printf("%d ",cnt); }