美文网首页信息学竞赛题解(IO题解)
BZOJ-1029: [JSOI2007]建筑抢修(贪心+优先队

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

作者: AmadeusChan | 来源:发表于2018-10-16 20:43 被阅读0次

    题目: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 ;
    }
    
    

    相关文章

      网友评论

        本文标题:BZOJ-1029: [JSOI2007]建筑抢修(贪心+优先队

        本文链接:https://www.haomeiwen.com/subject/volkzftx.html