建筑抢修

标志： 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 完全可以解决的。