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

標志： repair.*

問題描述：

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

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

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

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

?

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

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

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

?

樣例輸入：

4

100 200

200 1300

1000 1250

2000 3200

?

樣例輸出：

3

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

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

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

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

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