題目鏈接： 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
}
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
