| 题目名称 | 929. [JSOI 2007] 建筑抢修 |
|---|---|
| 输入输出 | repair.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 Makazeu
于2012-09-28加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：44， 提交：106， 通过率：41.51% | ||||
 new ioer |
100 | 0.054 s | 6.77 MiB | C++ |
 sssSSSay |
100 | 0.055 s | 2.23 MiB | C++ |
|
new ioer |
100 | 0.056 s | 6.80 MiB | C++ |
 可以的. |
100 | 0.098 s | 1.46 MiB | C++ |
|
可以的. |
100 | 0.118 s | 1.45 MiB | C++ |
 -1 |
100 | 0.118 s | 15.57 MiB | C++ |
 jmisnal |
100 | 0.127 s | 1.46 MiB | C++ |
 0 |
100 | 0.128 s | 1.46 MiB | C++ |
 Hzfengsy |
100 | 0.128 s | 2.01 MiB | C++ |
|
可以的. |
100 | 0.133 s | 1.31 MiB | C++ |
| 关于 建筑抢修 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
| ||||
|
| ||||
|
贪心。
按结束时间End排序。 讨论： 如果当前的时间加上已有的时间没有超过结束时间，那么Ans++； 如果超过了，把它和堆顶元素比较，若小于堆顶，则更新堆顶。 | ||||
甘罗
炽烈的爱
OIdiot-
经过了一场激烈的战斗，T部落消灭了所有z部落的入侵者。但是T部落的基地里已经有N个建筑设施受到了严重的损伤，如果不尽快修复的话，这些建筑设施将会完全毁坏。
现在的情况是：T部落基地里只有一个修理工人，虽然他能瞬间到达任何一个建筑，但是修复每个建筑都需要一定的时间。同时，修理工人修理完一个建筑才能修理下一个建筑，不能同时修理多个建筑。如果某个建筑在一段时间之内没有完全修理完毕，这个建筑就报废了。
你的任务是帮小刚合理的制订一个修理顺序，以抢修尽可能多的建筑。
输入格式：
第一行是一个整数N，接下来N行每行两个整数T1,T2描述一个建筑：修理这个建筑需要T1秒，如果在T2秒之内还没有修理完成，这个建筑就报废了。
输出格式：
输出一个整数S，表示最多可以抢修S个建筑。
样例输入：
4
100 200
200 1300
1000 1250
2000 3200
样例输出：
3
时间限制:
各个测试点2s
数据规模：
N<150000