P4053 [JSOI2007] 建筑抢修
时间限制: 1.00s 内存限制: 128.00MB
复制 Markdown
中文
退出 IDE 模式
题目描述
小刚在玩 JSOI 提供的一个称之为“建筑抢修”的电脑游戏：经过了一场激烈的战斗，T 部落消灭了所有 Z 部落的入侵者。但是 T 部落的基地里已经有 N 个建筑设施受到了严重的损伤，如果不尽快修复的话，这些建筑设施将会完全毁坏。现在的情况是：T 部落基地里只有一个修理工人，虽然他能瞬间到达任何一个建筑，但是修复每个建筑都需要一定的时间。同时，修理工人修理完一个建筑才能修理下一个建筑，不能同时修理多个建筑。如果某个建筑在一段时间之内没有完全修理完毕，这个建筑就报废了。你的任务是帮小刚合理的制订一个修理顺序，以抢修尽可能多的建筑。
输入格式
第一行，一个整数 N。
接下来 N 行，每行两个整数 T1,T2 描述一个建筑：修理这个建筑需要 T1 秒，如果在 T2 秒之内还没有修理完成，这个建筑就报废了。
输出格式
输出一个整数 S，表示最多可以抢修 S 个建筑。
输入输出样例
输入 #1复制运行
4 100 200 200 1300 1000 1250 2000 3200
输出 #1复制运行
3
说明/提示
对于 100% 的数据，1≤N<150000，1≤T1<T2<231。
贪心
大方向上我们肯定要按照t2 也就是等待时间排序 升序 然后当我们每碰到一个建筑的时候 如果可以直接修好 那肯定直接修好
当修不好的时候 我们有一种选择是直接放弃这个建筑 但是这样是不是最优的呢？ 如果直接放弃 那么答案数不变 花费的时间数相当于前面修了的建筑的时间数的和 但是如果我们建立一个堆 将所有前面修过的建筑和当前的建筑的花费时间存起来 然后取放弃一个时间最大的建筑 这个最大时间一定大于等于当前建筑 那么当前建筑就可以放入堆中 并且修理 这样答案数不变 但是所花费的时间一定是最少的 实现反悔贪心
#include <bits/stdc++.h> using namespace std; const int N=15e4+5; pair<long long,long long>a[N]; int n; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n; for(int i=1;i<=n;i++){ cin>>a[i].second>>a[i].first; } sort(a+1,a+1+n); priority_queue<long long>q; long long sum=0; int ans=0; for(int i=1;i<=n;i++){ sum+=a[i].second; q.push(a[i].second); if(sum<=a[i].first){ ans++; }else { if(!q.empty()) sum-=q.top(),q.pop(); } } cout<<ans<<'\n'; return 0; }
