[bzoj] 1029: [JSOI2007]建筑抢修

发表于   |   分类于   |  

题意

小刚在玩JSOI提供的一个称之为“建筑抢修”的电脑游戏：经过了一场激烈的战斗，T部落消灭了所有z部落的入侵者。但是T部落的基地里已经有N个建筑设施受到了严重的损伤，如果不尽快修复的话，这些建筑设施将会完全毁坏。现在的情况是：T部落基地里只有一个修理工人，虽然他能瞬间到达任何一个建筑，但是修复每个建筑都需要一定的时间。同时，修理工人修理完一个建筑才能修理下一个建筑，不能同时修理多个建筑。如果某个建筑在一段时间之内没有完全修理完毕，这个建筑就报废了。你的任务是帮小刚合理的制订一个修理顺序，以抢修尽可能多的建筑

传送门

分析

如果能修则修，如果不能修就用已用时间的最长时间判断是否可以更优

这个贪心可以用拟阵来证明,但是懒得写了.
拟阵的用法可以看《算法导论》或刘雨辰的集训队论文《对拟阵的初步研究》

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <cstdio>

int CH , NEG ;
inline void read(int& ret) {
    ret = NEG = 0 ; while (CH=getchar() , CH<'!') ;
    if (CH == '-') NEG = true , CH = getchar() ;
    while (ret = ret*10+CH-'0' , CH=getchar() , CH>'!') ;
    if (NEG) ret = -ret ;
}

#include <queue>
#include <algorithm>

#define  maxn  150010LL

struct NODE {
trueint t1 , t2 ;
truebool operator < (const NODE& b) const { return t2 < b.t2 ; }
} a[maxn] ;

std::priority_queue<int>q ;

int n , i , used ;
int main() {
//	#define READ
true#ifdef  READ
truetruefreopen(".in" ,"r",stdin ) ;
truetruefreopen(".out","w",stdout) ;
true#endif
trueread(n) ;
truefor (i = 1 ; i <= n ; i ++ )
truetrueread(a[i].t1) , read(a[i].t2) ;
truestd::sort(a+1 , a+n+1) ;
trueused = 0 ;
truefor (i = 1 ; i <= n ; i ++ )
truetrueif (used+a[i].t1 <= a[i].t2)
truetruetrueq.push(a[i].t1) , used += a[i].t1 ;
truetrueelse if (a[i].t1<q.top() && used+a[i].t1-q.top() <= a[i].t2)
truetruetrueused += a[i].t1-q.top() , q.pop() , q.push(a[i].t1) ;
trueprintf("%d\n", q.size()) ;
true#ifdef  READ
truetruefclose(stdin) ; fclose(stdout) ;
true#else
truetruegetchar() ; getchar() ;
true#endif
truereturn 0 ;
}

热评文章