[JSOI2007]建筑抢修 优先队列 贪心

#include<cstdio>#include<algorithm>#include<cstring>#include<queue>using namespace std;#define maxn 200000+4#define ll long longstruct WORK{ ?int cost,ed ; }work[maxn];bool cmp(WORK a,WORK b){ return a.ed<b.ed; }priority_queue<ll>Q;int main(){ ???//freopen("input.in","r",stdin); ???int n,ans=0; ???ll total=0; ???scanf("%d",&n); ???for(int i=1;i<=n;++i) scanf("%d%d",&work[i].cost,&work[i].ed); ???sort(work+1,work+1+n,cmp); ???for(int i=1;i<=n;++i){ ???????if(total+work[i].cost<=work[i].ed) ++ans, Q.push(work[i].cost), total+=work[i].cost; ???????else if(work[i].cost<Q.top()) total-=Q.top(),total+=work[i].cost,Q.pop(),Q.push(work[i].cost); ???} ???printf("%d",ans); ???return 0;}