BZOJ-1029: [JSOI2007]建筑抢修（贪心+优先队

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1029

首先按照t2升序排序，然后一个个试着去加，如果某一个无法完成，那么尝试删除之前完成且占用时间大于当前建筑的。用优先队列维护，最后留在队列里的数就是答案。

代码：

37d12f2eb9389b50ccd32a308735e5dde7116ea0.jpg.png

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
 
using namespace std ;
 
#define MAXN 150010
#define rep( i , x ) for ( int i = 0 ; i < x ; i ++ )
 
struct cmp {
    bool operator(  )( int x , int y ) {
        return x < y ;
    }
};
 
priority_queue< int , vector< int > , cmp > Q ;
 
struct node {
    int t1 , t2 ;
    bool operator < ( const node &a ) const {
        return t2 < a.t2 ;
    }
} a[ MAXN ] ;
 
int n , Time = 0 ;
 
int main(  ) {
    scanf( "%d" , &n ) ; rep( i , n ) scanf( "%d%d" , &a[ i ].t1 , &a[ i ].t2 ) ;
    sort( a , a + n ) ;
    while ( ! Q.empty(  ) ) Q.pop(  ) ;
    rep( i , n ) {
        if ( Time + a[ i ].t1 <= a[ i ].t2 ) {
            Time += a[ i ].t1 ; Q.push( a[ i ].t1 ) ;
        } else {
            while ( ! Q.empty(  ) && a[ i ].t1 < Q.top(  ) && Time + a[ i ].t1 > a[ i ].t2 ) Time -= Q.top(  ) , Q.pop(  ) ;
            if ( Time + a[ i ].t1 <= a[ i ].t2 ) Time += a[ i ].t1 , Q.push( a[ i ].t1 ) ;
        }
    }
    printf( "%d\n" , Q.size(  ) ) ;
    return 0 ;
}