3829 - 建筑抢修
时间限制 : 1 秒
内存限制 : 128 MB
小刚在玩JSOI提供的一个称之为“建筑抢修”的电脑游戏：经过了一场激烈的战斗，T部落消灭了所有z部落的入侵者。但是T部落的基地里已经有N个建筑设施受到了严重的损伤，如果不尽快修复的话，这些建筑设施将会完全毁坏。现在的情况是：T部落基地里只有一个修理工人，虽然他能瞬间到达任何一个建筑，但是修复每个建筑都需要一定的时间。同时，修理工人修理完一个建筑才能修理下一个建筑，不能同时修理多个建筑。如果某个建筑在一段时间之内没有完全修理完毕，这个建筑就报废了。你的任务是帮小刚合理的制订一个修理顺序，以抢修尽可能多的建筑。
题目输入
第一行是一个整数N，接下来N行每行两个整数T1,T2描述一个建筑：修理这个建筑需要T1秒，如果在T2秒之内还没有修理完成，这个建筑就报废了。
题目输出
输出一个整数S，表示最多可以抢修S个建筑。 数据范围： N<150000，T1
输入/输出样例
输入格式
4 100 200 200 1300 1000 1250 2000 3200
输出格式
3
C++解答
#define MAXN 150010UL #define ll long long #include <algorithm> #include <cstdio> #include <queue> struct Point{ ll t1,t2; friend bool operator < (Point a,Point b){return a.t1<b.t1;} inline void in(){scanf("%lld%lld",&t1,&t2);return;} }; std::priority_queue<Point> que; Point s[MAXN]; int n,i; ll cur_time; inline bool comp(Point a,Point b){return a.t2<b.t2;} int main(){ scanf("%d",&n); for(;i<n;i++) s[i].in(); for(std::sort(s,s+n,comp),i=0;i<n;i++){ if(cur_time+s[i].t1<=s[i].t2) que.push(s[i]),cur_time+=s[i].t1; else if(s[i].t1<=que.top().t1&&cur_time+s[i].t1-que.top().t1<=s[i].t2) cur_time+=s[i].t1-que.top().t1,que.pop(),que.push(s[i]); } printf("%d",que.size()); return 0; }