题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1029
这道题好像是一道比较经典的贪心，最主要的思路是用堆来提供反悔，修正决策的途径。
我们首先按每个建筑的最晚修复时间排序。然后扫过去，能修就修，并且将修过建筑所用的时间加入到堆里面。
如果遇到了不能修的情况，我们看一下堆顶元素花费的时间与当前所需要的时间的大小关系，如果堆顶元素更大，那么我们反悔，不修之前那个建筑，把时间省下来修当前的建筑，然后把所需时间加入堆中。这样就完成了一次决策的修正。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<queue> 5 using namespace std; 6 typedef long long ll; 7 int inline readint(){ 8 ????int Num;char ch; 9 ????while((ch=getchar())<‘0‘||ch>‘9‘);Num=ch-‘0‘;10 ????while((ch=getchar())>=‘0‘&&ch<=‘9‘) Num=Num*10+ch-‘0‘;11 ????return Num;12 }13 int N;14 struct Building{15 ????int t1,t2;16 ????bool operator < (const Building &_)const{17 ????????return t2<_.t2;18 ????}19 }A[150010];20 priority_queue <int> q;21 int main(){22 ????N=readint();23 ????for(int i=1;i<=N;i++){24 ????????A[i].t1=readint();25 ????????A[i].t2=readint();26 ????}27 ????sort(A+1,A+1+N);28 ????ll ti=0;29 ????int ans=0;30 ????for(int i=1;i<=N;i++){31 ????????if(ti+A[i].t1<=A[i].t2){32 ????????????ti+=A[i].t1;33 ????????????q.push(A[i].t1);34 ????????????ans++;35 ????????}36 ????????else{37 ????????????int tmp=q.top();38 ????????????if(tmp>A[i].t1){39 ????????????????q.pop();40 ????????????????ti-=tmp-A[i].t1;41 ????????????????q.push(A[i].t1);42 ????????????}43 ????????}44 ????}45 ????printf("%d\n",ans);46 ????return 0;47 } [BZOJ1029][JSOI2007]建筑抢修 贪心+堆
原文地址：http://www.cnblogs.com/halfrot/p/7608530.html