题意:一辆卡车距离重点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 ;
}
 

最新文章

  1. CSS 代码技巧与维护 ★ Mozilla Hacks – the Web developer blog
  2. POJ 1681 Painter&#39;s Problem (高斯消元)
  3. Wampserver2.5配置虚拟主机出现403 Forbidden解决办法
  4. ViewModel在MVC3中的应用:实现多字段表格的部分更新
  5. oracle 备份和还原还有创建用户、表空间、授权
  6. [ZZ]如果有人问你数据库的原理,叫他看这篇文章
  7. HDU 5052 Yaoge’s maximum profit 光秃秃的树链拆分 2014 ACM/ICPC Asia Regional Shanghai Online
  8. Elmah错误日志工具
  9. [转载]PS各个工具的字母快捷键和英文全名
  10. Elasticsearch(GEO)空间检索查询
  11. google C++编程风格指南之头文件的包括顺序
  12. tomcat 热替换class
  13. LeetCode(32)-Binary Tree Level Order Traversal
  14. redis结合自定义注解实现基于方法的注解缓存,及托底缓存的实现
  15. 手动增加swap空间
  16. Linux 学习笔记 2:文件系统
  17. 高性能Javascript(1)
  18. Git 推送操作
  19. 接口自动化(unittest)
  20. JS中的history对象

热门文章

  1. 16进制 ,Color,Colour转换
  2. Reverse and Compare(DP)
  3. EasyNVR和EasyDSS云平台联手都不能解决的事情,只有国标GB28181能解决了
  4. 注册Asp4.0到iis
  5. 《挑战程序设计竞赛》2.2 贪心法-区间 POJ2376 POJ1328 POJ3190
  6. linux 服务器所支持的最大句柄数调高数倍(与服务器的内存数量相关)
  7. 实用 35 个 jQuery 小技巧
  8. SpringBoot连接PostgreSQL
  9. asp.net 站点公布
  10. C++ Primer笔记14_面向对象程序设计