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

標(biāo)志： repair.*

問題描述：

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

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

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

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

?

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

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

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

?

樣例輸入：

4

100 200

200 1300

1000 1250

2000 3200

?

樣例輸出：

3

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

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

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

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

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