?????????????????????????????????????????? 建筑搶修

標志： repair.*

問題描述：

小剛在玩 JSOI 提供的一個稱之為“建筑搶修”的電腦游戲。

經(jīng)過了一場激烈的戰(zhàn)斗， T 部落消滅了所有 z 部落的入侵者。但是 T 部落的基地里已經(jīng)有 N 個建筑設(shè)施受到了嚴重的損傷，如果不盡快修復(fù)的話，這些建筑設(shè)施將會完全毀壞。

現(xiàn)在的情況是： T 部落基地里只有一個修理工人。雖然它能瞬間到達任何一個建筑，但是修復(fù)每個建筑都需要一定的時間。同時，修理工人修理完一個建筑才能修理下一個建筑，不能同時修理多個建筑。如果某個建筑在一段時間之內(nèi)沒有完全修理完畢，這個建筑就報廢了。

你的任務(wù)是幫小剛合理的制定一個修理順序，以搶修盡可能多的建筑。

?

輸入文件第一行是一個整數(shù) N ，接下來 N 行每行兩個整數(shù) T1, T2 描述一個建筑：修理這個建筑需要 T1 秒，如果在 T2 秒之內(nèi)還沒有修理完成，這個建筑就報廢了。

輸出文件只有一行，是一個整數(shù) S ，表示最多可以搶修 S 個建筑。

N < 150,000;? T1 < T2 < maxlongint

?

樣例輸入：

4

100 200

200 1300

1000 1250

2000 3200

?

樣例輸出：

3

?? 本題非常具有迷惑性。如果將所有建筑的 T2 值升序排列的話，則修理建筑的決策是有序的，因此誘導(dǎo)我們向動態(tài)規(guī)劃的思路上去考慮。但實質(zhì)上，經(jīng)過多次努力，動態(tài)規(guī)劃算法無一例外是超時的——考慮 3 個變量：當前建筑 n ，已經(jīng)修理的建筑數(shù)目 m ，已經(jīng)花去的時間 t ，這 3 個量中只有一個可以作為函數(shù)值，而其他的兩個量必須作為二維變量，狀態(tài)數(shù)太多了??！

? 巨大的數(shù)據(jù)規(guī)模不得不讓我們向貪心法的思路去看。首先由一點，那就是工人一旦開始工作就不能停止，這是顯然的。如果采用增量的思路的話，假設(shè)前 m 個建筑中最多修理 k 個建筑，同時所用的時間最少，我們來看一看再增加一個建筑時會發(fā)生什么事情。

1、 如果再增加一個建筑，修建的時間不超過題目要求，那就添上去；

2、 否則，應(yīng)將該建筑去替換一個已有的最長 T1 時間的建筑，以節(jié)省總時間（在可修建筑數(shù)目不變的情況下），除非該建筑本身就是 T1 時間最長的。

這個貪心思路可以用歸納法證明是正確的。實現(xiàn)時，應(yīng)該用堆結(jié)構(gòu)來保存要修的建筑的時間，時間復(fù)雜度是 O(nlog₂n) ， 1s 完全可以解決的。