首页 > 代码库 > [POJ 2431]Expedition
[POJ 2431]Expedition
1、题目连接:http://poj.org/problem?id=2431
2、题目大意:你需要开着一辆卡车行驶L单位距离,最开始卡车有P单位汽油,卡车每开一单位距离需要消耗1单位汽油,如果在中途卡车汽油耗尽,卡车就无法继续前行,到不了终点,在途中一共有n个加油站,告诉你每个加油站距离终点的距离和每个加油站可以加的油量,假设卡车的油箱是无穷大的,问卡车至少要加多少次油才能到达终点?卡车到不了终点输出-1
3、题目思路:使用优先队列+贪心思想完成此题,队列中维护到达目前的加油站之前没有用过的加油站,保证队首的加油站可以加的油最多,如果当前油箱内的油量不够到达当前加油站,就从优先队列队首取出一个未用过的加油站加油。如果需要加油时队列为空,则卡车到不了终点
4、代码:
#include <stdio.h> #include <string.h> #include <algorithm> #include <queue> #define MAXN 10010 using namespace std; struct info { int a,b; //a[i]=第i个加油站和起点之间的距离,b[i]=第i个加油站的油量 }station[MAXN]; priority_queue<int>heap; bool cmp(info x,info y) { return x.a<y.a; } int main() { int n,l,p; scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d%d",&station[i].a,&station[i].b); scanf("%d%d",&l,&p); for(int i=0;i<n;i++) station[i].a=l-station[i].a; int ans=0,pos=0,tank=p; //ans-加油次数,pos-当前位置,tank-剩余油量 station[n].a=l; //为了便于处理,把终点也看成一个加油站 station[n].b=0; n++; sort(station,station+n,cmp); for(int i=0;i<n;i++) { int dist=station[i].a-pos; //dist=接下来要前行的距离 while(tank-dist<0) //油箱里的油不够就不断加,只加最大的加油站里的油 { if(heap.empty()) //没有可选的加油站,没油走不了了 { printf("-1\n"); return 0; } tank+=heap.top(); heap.pop(); ans++; } tank-=dist; //走到下一站,油箱中的油量减少 pos=station[i].a; heap.push(station[i].b); } printf("%d\n",ans); return 0; }
[POJ 2431]Expedition
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。