这题说的是 一辆汽车 每走一单位的距离就消耗一单位的燃料,然后,他要回城里去,当然他与城镇之间有n个加油站 ,他的油箱可以为 无穷大 ,这样分析后发现进不进汽油站 与 汽油站在哪无关 ,只与加油站的 汽油有关 (当然是他能到达的加油站)然后直接贪心

#include<string.h>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
struct point {
int dist,pow,num;
bool operator <(const point &b) const{
if(pow<b.pow) return true;
else return false;
}
};
point P[100005];
bool cmp(point a,point b)
{
if(a.dist>b.dist) return true;
else return false;
}
bool mark[100005];
int main()
{
int i,n,num;
point T,W;
priority_queue<point>Q;
while(scanf("%d",&n)==1){
while(!Q.empty())Q.pop();
num=0;
memset(mark,true,sizeof(mark));
for(i=0;i<n;i++)
scanf("%d%d",&P[i].dist,&P[i].pow);
sort(P,P+n,cmp);
scanf("%d%d",&T.dist,&T.pow);
for(i=0;i<n;i++)
P[i].num=i;
T.num=-1;
Q.push(T);
while(!Q.empty()){
Q.pop();
if(T.pow>=T.dist) break;
for(i=T.num+1;i<n;i++)
if(T.pow-(T.dist-P[i].dist)>=0&&mark[i]){
Q.push(P[i]);
mark[i]=0;
}
if(Q.empty()) break;
W=Q.top();
if(W.dist>T.dist){
T.pow+=W.pow;
}
else{
W.pow+=T.pow-(T.dist-W.dist);
T=W;
}
num++;
if(T.pow>=T.dist) break; }
if(T.pow>=T.dist)printf("%d\n",num);
else printf("-1\n");
}
return 0;
}

最新文章

  1. 参考bootstrap中的popover.js的css画消息弹框
  2. 关于mongodb的复合索引新功能
  3. Android 的 AlarmManager 和 wakeLock联合使用
  4. Leetcode Binary Tree Postorder Traversal
  5. PHP IDE phpstorm 快捷键
  6. mongoose find查询意错点
  7. yum downloadonly
  8. J2SE J2EE J2ME的区别
  9. RedHat6配置yum源 (32位)
  10. HW2.8
  11. C#中同时使用Lambda表达式和递归
  12. iOS RTMP 视频直播开发笔记(1) – 采集摄像头图像
  13. Python函数式编程:内置filter函数使用说明
  14. 谈谈一些有趣的CSS题目(十三)-- 巧妙地制作背景色渐变动画!
  15. 堆结构的优秀实现类----PriorityQueue优先队列
  16. IntelliJ IDEA光标变粗 backspace无法删除内容解决方法
  17. 一款Android图文识别与扫描软件
  18. shell编程 之 文件包含
  19. 重建索引解决mssql表查询超时的问题
  20. 《剑指offer》-链表找环入口

热门文章

  1. [工具] 将Sublime Text 3配置为C++代码编辑器
  2. jmeter函数助手之time函数实操
  3. Xcode - Debug汇编模式切换调试
  4. jQuery里面ajax请求的封装
  5. 51单片机之IIC通信原理及软件仿真
  6. python操作数据库PostgreSQL
  7. vue之介绍
  8. ICSharpCode.SharpZipLib.dll 压缩多文件
  9. pdb学习笔记
  10. Xcode 9运行h d f报错