POJ 2431 贪心+优先队列
2024-08-30 19:04:56
题意:一辆卡车距离重点L,现有油量P,卡车每前行1米耗费油量1,途中有一些加油站,问最少在几个加油站加油可使卡车到达终点或到达不了终点。
思路:运用优先队列,将能走到的加油站的油量加入优先队列中,油不够时加入优先队列中数值最大的油,如果油不够时队列里为空则到达不了。
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
priority_queue<int> que;
struct Stop {
int dis,fuel;
}stop[];
bool cmp (Stop a,Stop b) {
if(a.dis==b.dis) return a.fuel>b.fuel;
return a.dis<b.dis;
}
int main() {
int n,L,p;
while(~scanf("%d",&n)) {
for(int i=;i<n;i++) {
scanf("%d%d",&stop[i].dis,&stop[i].fuel);
}
scanf("%d%d",&L,&p);
for(int i=;i<n;i++) {
stop[i].dis=L-stop[i].dis;
}
sort(stop,stop+n,cmp);
stop[n].dis=L;stop[n].fuel=;
int cnt=,pos=,flag=;
for(int i=;i<=n;i++) {
int d=stop[i].dis-pos;
while(p<d) {
if(!que.empty()) {
p+=que.top();
que.pop();
cnt++;
}else break;
}
if(p<d) {
flag=;
puts("-1");break;
}
p-=d;
que.push(stop[i].fuel);
pos=stop[i].dis;
}
if(flag==) printf("%d\n",cnt);
while(!que.empty()) que.pop();
}
return ;
}
最新文章
- CSS 代码技巧与维护 ★ Mozilla Hacks – the Web developer blog
- POJ 1681 Painter&#39;s Problem (高斯消元)
- Wampserver2.5配置虚拟主机出现403 Forbidden解决办法
- ViewModel在MVC3中的应用:实现多字段表格的部分更新
- oracle 备份和还原还有创建用户、表空间、授权
- [ZZ]如果有人问你数据库的原理,叫他看这篇文章
- HDU 5052 Yaoge’s maximum profit 光秃秃的树链拆分 2014 ACM/ICPC Asia Regional Shanghai Online
- Elmah错误日志工具
- [转载]PS各个工具的字母快捷键和英文全名
- Elasticsearch(GEO)空间检索查询
- google C++编程风格指南之头文件的包括顺序
- tomcat 热替换class
- LeetCode(32)-Binary Tree Level Order Traversal
- redis结合自定义注解实现基于方法的注解缓存,及托底缓存的实现
- 手动增加swap空间
- Linux 学习笔记 2:文件系统
- 高性能Javascript(1)
- Git 推送操作
- 接口自动化(unittest)
- JS中的history对象
热门文章
- 16进制 ,Color,Colour转换
- Reverse and Compare(DP)
- EasyNVR和EasyDSS云平台联手都不能解决的事情,只有国标GB28181能解决了
- 注册Asp4.0到iis
- 《挑战程序设计竞赛》2.2 贪心法-区间 POJ2376 POJ1328 POJ3190
- linux 服务器所支持的最大句柄数调高数倍(与服务器的内存数量相关)
- 实用 35 个 jQuery 小技巧
- SpringBoot连接PostgreSQL
- asp.net 站点公布
- C++ Primer笔记14_面向对象程序设计