Time Limit:?4 Sec??Memory Limit:?162 MB
Submit:?4452??Solved:?2006

Description

　　小剛在玩JSOI提供的一個稱之為“建筑搶修”的電腦游戲：經過了一場激烈的戰斗，T部落消滅了所有z部落的
入侵者。但是T部落的基地里已經有N個建筑設施受到了嚴重的損傷，如果不盡快修復的話，這些建筑設施將會完全
毀壞。現在的情況是：T部落基地里只有一個修理工人，雖然他能瞬間到達任何一個建筑，但是修復每個建筑都需
要一定的時間。同時，修理工人修理完一個建筑才能修理下一個建筑，不能同時修理多個建筑。如果某個建筑在一
段時間之內沒有完全修理完畢，這個建筑就報廢了。你的任務是幫小剛合理的制訂一個修理順序，以搶修盡可能多
的建筑。

Input

　　第一行是一個整數N接下來N行每行兩個整數T1,T2描述一個建筑：修理這個建筑需要T1秒，如果在T2秒之內還
沒有修理完成，這個建筑就報廢了。

Output

　　輸出一個整數S，表示最多可以搶修S個建筑.N < 150,000;? T1 < T2 < maxlongint

Sample Input

4
100 200
200 1300
1000 1250
2000 3200

Sample Output

3

HINT

Source

?

貪心

憑感覺盲狙了兩個貪心方案：

1、按結束時間排序，能修就修。不能修的時候，如果不修之前耗時最多的那個就能讓這個被修好，就用這個替換耗時最多的建筑。

WA

2、發現并不需要當前這個一定被修好，只要用這個替換之前耗時最多的，能讓累計耗時減少，就替換。

AC

1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<queue> 8 #include<vector> 9 #define LL long long 10 using namespace std; 11 const int mxn=200010; 12 int read(){ 13 int x=0,f=1;char ch=getchar(); 14 while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();} 15 while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();} 16 return x*f; 17 } 18 struct task{ 19 int t1,t2; 20 }a[mxn]; 21 int cmp(const task a,const task b){ 22 return a.t2<b.t2; 23 } 24 priority_queue<int>q; 25 int n; 26 int ans=0; 27 int main(){ 28 int i,j; 29 n=read(); 30 for(i=1;i<=n;i++){ 31 a[i].t1=read();a[i].t2=read(); 32 } 33 sort(a+1,a+n+1,cmp); 34 int now=0; 35 for(i=1;i<=n;i++){ 36 if(a[i].t1+now<=a[i].t2){ 37 now+=a[i].t1; 38 q.push(a[i].t1); 39 ++ans; 40 } 41 else if(!q.empty()){ 42 int tmp=q.top(); 43 if(tmp>a[i].t1){ 44 now=now-tmp+a[i].t1; 45 q.pop(); 46 q.push(a[i].t1); 47 } 48 } 49 } 50 printf("%d\n",ans); 51 return 0; 52 }

?

轉載于:https://www.cnblogs.com/SilverNebula/p/6639887.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的Bzoj1029 [JSOI2007]建筑抢修的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。