题目: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 ;
}
网友评论