【贪心】POJ 2431：Expedition

2024-03-08 21:32

文章标签 贪心 poj expedition 2431

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

一、题目内容

POJ 2431 原题地址

二、题意解释

一辆卡车，初始时，距离终点L，油量为P，在起点到终点途中有n个加油站，每个加油站油量有限，而卡车的油箱容量无限.
卡车在行车途中，每走一个单位的距离消耗一个单位的油量，给定n个加油站距离终点的距离以及油存储量。
问卡车是否能到达终点，如果可达，最少需要加多少次油，否则输出-1.

三、代码及注释

#include<stdio.h>
#include<queue>
#include<algorithm>
using namespace std;
int N,L,P;
struct station{int a,b;//a为与起始位置的距离，b为油量bool operator < (const station& A) const{return a<A.a;}
}st[10005];
priority_queue<int> Q;
void solve()
{scanf("%d",&N);for(int i=0; i<N; i++){scanf("%d%d",&st[i].a,&st[i].b);}scanf("%d%d",&L,&P);//这里注意，输入的a起初是距离town的距离，需要通过L-a变成距离现在位置的距离for(int i=0; i<N; i++){st[i].a=L-st[i].a;}int ans=0,pos=0,tank=P;st[N].a=L;st[N].b=0;N++;sort(st,st+N);for(int i=0; i<N; i++){int t=st[i].a-pos;//贪心，只有在油不足时才加油，且加最大的油while(tank<t){if(Q.empty())//如果为空，说明没油可加，输出-1{printf("%d",-1);return;}tank+=Q.top();Q.pop();ans++;}tank-=t;Q.push(st[i].b);pos=st[i].a;}printf("%d\n",ans);
}
int main()
{solve();return 0;
}