首页 > 代码库 > POJ2431 Expedition (优先队列)
POJ2431 Expedition (优先队列)
题目链接:
http://poj.org/problem?id=2431
题意:
一条路上有n个加油站,终点离起点的距离为L,然n个加油站离终点的距离为a[i],每个加油站可以给汽车加b[i]的油,
问最少加多少次可以到达终点,不能到达终点输出-1。
分析:
要想最少我们肯定是在马上要没有的时候加油,然后每次加的应该是最多的油。
因此我们走过第i个加油站的时候,把b[i]放入优先队列里,然后不能到达的时候
每次取出一个直到可以到达当前的位置,如果队列为空而且还不能动到达当前
位置则永远不可达。
代码如下:
#include <iostream> #include <cstdio> #include <queue> #include <algorithm> using namespace std; const int maxn = 1000010; struct stop { int a,b; bool operator <(const struct stop &tmp)const { return a<tmp.a; } } p[maxn]; int n,l,pp; void solve() { p[n].a=l,p[n].b=0; sort(p,p+n+1); int tot = pp; priority_queue<int >Q; while(!Q.empty()) Q.pop(); int ans = 0,pos=0,tag=0; for(int i=0; i<=n; i++) { int dis = p[i].a-pos; while(tot<dis) { if(Q.empty()) { printf("-1\n"); return; } tot+=Q.top(); Q.pop(); ans++; } tot-=dis; pos=p[i].a; Q.push(p[i].b); //printf("tot: %d\n",tot); } printf("%d\n",ans); return ; } int main() { while(~scanf("%d",&n)) { int a,b; for(int i=0; i<n; i++) scanf("%d%d",&p[i].a,&p[i].b); scanf("%d%d",&l,&pp); for(int i=0; i<n; i++) p[i].a=l-p[i].a; solve(); } return 0; } /*** 4 4 4 5 2 11 5 15 10 25 10 ***/
POJ2431 Expedition (优先队列)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。