[luogu4053 JSOI2007] 建筑抢修 (贪心 优先队列)
2024-09-01 16:55:41
题目描述
小刚在玩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
说明
N < 150,000; T1 < T2 < maxlongint
题解
光按t2贪心显然不行,那么应该考虑解决贪心失败的情况
显然是涉及了t1的问题——让一个t1更小进去显然更优(同样的维修数用时更少)
那么用个优先队列记录前面的最大t1值当当前t2进行不下去且当前t1小于之前的最大的就把这个t1换进去
然后跑完就好啦(~ ̄▽ ̄)~
code:
//By Menteur_Hxy
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define LL long long
using namespace std;
const int N=150010;
int n;
struct blo{
LL t1,t2;
}B[N];
bool cmp(blo a,blo b) {
return a.t2<b.t2;
}
priority_queue<int> Q;
int main() {
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lld %lld",&B[i].t1,&B[i].t2);
sort(B+1,B+1+n,cmp);
LL now=0,ans=0;
for(int i=1;i<=n;i++) {
if(B[i].t2>=now+B[i].t1) ans++,now+=B[i].t1,Q.push(B[i].t1);
else {
LL ret=Q.top();
if(ret>B[i].t1) {
Q.pop();
Q.push(B[i].t1);
now-=ret-B[i].t1;
}
}
}
printf("%lld",ans);
return 0;
}
最新文章
- C/C++ 中判断某一文件或目录是否存在
- APP标配控制器:UINavigationController
- PHP 语法
- 调试WEB APP多设备浏览器
- shell 块注释
- Codeforces Gym 100342J Problem J. Triatrip 三元环
- hdu 1540 Tunnel Warfare (区间线段树(模板))
- [zz] makefile中=和:=的区别
- TinyXml 快速入门(三)
- C++中如何建立一个顺序表
- java操作mongodb——查询数据
- java基础数据类型包装类
- CentOS 7 安装 Nginx 反向代理 node
- iot:下一步要做的工作
- LeetCode算法题-Merge Two Binary Trees(Java实现)
- Java实现Sunday百万级数据量的字符串快速匹配算法
- ASP.NET Core托管和部署Linux实操演练手册
- Hive介绍和Hive环境搭建
- WPF转换器:时间转换为字符串
- template.js 模版内调用外部JS方法
热门文章
- MYSQL 源码解读系列 [线程池。。] ----dennis的博客
- PHP扩展开发--实验成功
- Meteor 前端 RESTful API 通过后端 API 下载文件
- [Python] Create a minimal website in Python using the Flask Microframework
- impdp时卡住,DW等待library cache lock
- Netty In Action中文版 - 第十五章:选择正确的线程模型
- swing Jlable中存放变量显示问题
- 【数据结构与算法】(二) c 语言链表的简单操作
- chrome 插件开发2
- Mysql 索引需要了解的几个注意