题意：

抢修N个建筑。修理工人一次只能修理一个建筑，如果某个建筑在一段时间之内没有完全修理完毕，这个建筑就报废了。求一个能抢修尽可能多的建筑的抢修顺序。

题解：

贪心。首先按毁坏时间排序，如果按照当前的时间计算能修好这个建筑，就修好它；如果修不好，就找以前修过的建筑，如果修理时间最长的建筑比它修理时间长，就不修这个建筑，改修当前建筑，使当前时间缩短。这个操作用优先队列维护。

代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #define inc(i,j,k) for(int i=j;i<=k;i++)using namespace std;struct task{
   int t1,t2;}; task tasks[200000];bool cmp(task a,task b){
   return a.t2
         
          
            q;int n,tim,ans,a;int main(){ scanf("%d",&n); inc(i,1,n)scanf("%d%d",&tasks[i].t1,&tasks[i].t2); sort(tasks+1,tasks+n+1,cmp); tim=ans=0; inc(i,1,n){ if(tim+tasks[i].t1<=tasks[i].t2)tim+=tasks[i].t1,q.push(tasks[i].t1),ans++; else if(!q.empty()&&tasks[i].t1<(a=q.top())&&tim-a+tasks[i].t1<=tasks[i].t2) tim=tim-a+tasks[i].t1,q.pop(),q.push(tasks[i].t1); } printf("%d",ans); return 0;}
          
         
        
       
      
     

 

20160517