2431Expedition POJ- 优先队列 + 贪心

本文主要是介绍2431Expedition POJ- 优先队列 + 贪心，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

该题需要注意的问题

题目给的加油站是到目的地的距离而不是距离起始点的距离

贪心策略，每次耗尽当前所有油，找路过所有加油站的能添加最大油量的那一家，加油，之后再走，在这个过程中不断将沿途经过的加油站添加到队列

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define MAXD 1000000 + 10
struct Car{int dist;int oil;
}point[MAXD];
bool cmp(Car p,Car q){if(p.dist < q.dist)return true;else if(p.dist > q.dist)return false;else if(p.oil  > q.oil)return true;elsereturn false;
}
int main(){int N;priority_queue<int,vector<int>, less<int> >q;scanf("%d",&N);for(int i = 0; i < N ; i++)scanf("%d%d",&point[i].dist,&point[i].oil);int L,P;scanf("%d%d",&L,&P);for(int i = 0; i < N ;i ++)point[i].dist = L - point[i].dist;sort(point,point + N,cmp);int pos = 0;int i = 0;int ans = 0;int ok = 1;while(pos < L){pos = pos + P;if(pos >= L) break;if(pos < L && i == N){ok = 0;break;}for(; i < N && point[i].dist <= pos; i++)q.push(point[i].oil);if(q.empty()){/*注意，如果没有加油站可以停就说明没法前进*/ok = 0 ;break;}P = q.top();q.pop();ans ++;}if(ok)printf("%d\n",ans);else  printf("-1\n");return 0;
}

这篇关于2431Expedition POJ- 优先队列 + 贪心的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---