题目名称 929. [JSOI2007] 建筑抢修
输入输出 repair.in/out
难度等级 ★★★
时间限制 1000 ms (1 s)
内存限制 128 MB
测试数据 10 简单对比
题目来源 2012-09-28
开放分组 全部用户
提交状态
分类标签
贪心法 栈和队列
通过:39, 提交:106, 通过率:36.79%
Gravatarnew ioer 100 0.054 s C++
GravatarsssSSSay 100 0.055 s C++
Gravatarnew ioer 100 0.056 s C++
Gravatar可以的. 100 0.098 s C++
Gravatar可以的. 100 0.118 s C++
Gravatar-1 100 0.118 s C++
Gravatarjmisnal 100 0.127 s C++
Gravatar0 100 0.128 s C++
GravatarHzfengsy 100 0.128 s C++
Gravatar可以的. 100 0.133 s C++
关于 建筑抢修 的讨论
贪心。
按结束时间End排序。
讨论:
如果当前的时间加上已有的时间没有超过结束时间,那么Ans++;
如果超过了,把它和堆顶元素比较,若小于堆顶,则更新堆顶。
GravatarOIdiot
2014-04-08 13:22 1楼
Gravatar炽烈的爱
2015-10-31 19:10 2楼
Gravatar甘罗
2016-10-14 21:00 3楼

929. [JSOI2007] 建筑抢修

★★★   输入文件:repair.in   输出文件:repair.out   简单对比
时间限制:1 s   内存限制:128 MB
经过了一场激烈的战斗,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