那么我们考虑优化贪心思想。

按照报废时间从小到大修，如果有一个会爆掉就从已经修好的中间找一个修理时间最长的不修，改修当前这个。

用优先队列维护一下当前修过的即可。

#include<bits/stdc++.h> using namespace std; #define int long long inline int read() { int f=1,w=0;char x=0; while(x<'0'||x>'9') {if(x=='-') f=-1; x=getchar();} while(x!=EOF&&x>='0'&&x<='9') {w=(w<<3)+(w<<1)+(x^48);x=getchar();} return w*f; } const int N=2e5+10; int n,ST,Cnt; struct Build { int T,Lim; inline bool operator < (const Build y) const { return T<y.T; } } p[N]; priority_queue<Build> Q; inline bool Cmp(Build x,Build y) {return x.Lim<y.Lim;} signed main(){ #ifndef ONLINE_JUDGE freopen("A.in","r",stdin); #endif n=read(); for(int i=1;i<=n;i++) p[i].T=read(),p[i].Lim=read(); sort(p+1,p+n+1,Cmp); for(int i=1;i<=n;i++) if(ST+p[i].T>p[i].Lim) { if(p[i].T<Q.top().T) ST=ST-Q.top().T+p[i].T,Q.pop(),Q.push(p[i]); } else Q.push(p[i]),Cnt++,ST+=p[i].T; printf("%lld\n",Cnt); }

$[JSOI2007]$建筑抢修

标签：

原文地址：https://www.cnblogs.com/wo-shi-zhen-de-cai/p/11798326.html