题目链接： http://www.lydsy.com/JudgeOnline/problem.php?id=1029
小刚在玩JSOI提供的一个称之为“建筑抢修”的电脑游戏：经过了一场激烈的战斗，T部落消灭了所有z部落的入侵者。但是T部落的基地里已经有N个建筑设施受到了严重的损伤，如果不尽快修复的话，这些建筑设施将会完全毁坏。现在的情况是：T部落基地里只有一个修理工人，虽然他能瞬间到达任何一个建筑，但是修复每个建筑都需要一定的时间。同时，修理工人修理完一个建筑才能修理下一个建筑，不能同时修理多个建筑。如果某个建筑在一段时间之内没有完全修理完毕，这个建筑就报废了。你的任务是帮小刚合理的制订一个修理顺序，以抢修尽可能多的建筑。
Input
第一行是一个整数N，接下来N行每行两个整数T1,T2描述一个建筑：修理这个建筑需要T1秒，如果在T2秒之内还没有修理完成，这个建筑就报废了。
Output
输出一个整数S，表示最多可以抢修S个建筑。 数据范围： N<150000
算法分析：首先贪心排序一下，优先选择更早修理完成的建筑（即优先选择T2小的），本以为这样就可以了，交了几次都WA了，仔细想了想，如果当前这个建筑来不及修好，可是之前修好的建筑里面有一个建筑修理时间比它长，那么我们放弃修理原来那个修理时间长的，转而修理当前这个建筑，那么，在当前修理建筑个数不变的情况下，用的时间会更少，于是，用优先队列保存一下原来修好了的建筑修理时间，然后，跟着上面那个思想处理一下就OK了。
1
#include<iostream>
2
#include<cstdio>
3
#include<cstring>
4
#include<cstdlib>
5
#include<cmath>
6
#include<algorithm>
7
#include<queue>
8
#define
inf 0x7fffffff
9
using
namespace
std;
10
const
int
maxn=
150000
+
100
;
11
12
int
n;
13
struct
node
14
{
15
int
num,r;
16
friend
bool
operator
<
(node a,node b)
17
{
18
return
a.r<
b.r;
19
}
20
}an[maxn];
21
22
priority_queue<
int
>
Q;
23
int
main()
24
{
25
while
(scanf(
"
%d
"
,&n)!=
EOF)
26
{
27
for
(
int
i=
0
;i<n ;i++) scanf(
"
%d%d
"
,&an[i].num,&
an[i].r);
28
sort(an,an+
n);
29
while
(!
Q.empty()) Q.pop() ;
30
int
ans=
0
,e=
0
;
31
for
(
int
i=
0
;i<n ;i++
)
32
{
33
if
(an[i].r-an[i].num+
1
>
e)
34
{
35
e +=
an[i].num;
36
Q.push(an[i].num);
37
ans++
;
38
}
39
else
40
{
41
if
(Q.empty())
continue
;
42
int
t=
Q.top() ;
43
if
(t>
an[i].num)
44
{
45
e -= t ;e +=
an[i].num;
46
Q.pop() ;Q.push(an[i].num);
47
}
48
}
49
}
50
printf(
"
%d\n
"
,ans);
51
}
52
return
0
;
53
}
