Expedition （POJ 2431）
题意：你需要驾驶一辆卡车行驶L单位长度。最开始的时候，卡车上有P单位的油。卡车每开1单位距离需要消耗1单位的汽油。如果在途中车上汽油耗尽，卡车就无法继续前行，因而无法到达终点。在途中一共有n个加油站。第i个加油站在距离起点Ai单位长度的地方，最多可以给汽车加油Bi单位的汽油。假设卡车的燃油箱的容量是无限大的，无论加多少油都没有关系。那么请问卡车是否能到达终点？如果可以，最少需要加多少次油？不能到达就输出-1。
思路：我们什么时候需要加油呢？肯定没油或者说是剩余的油量不能够使得卡车到达下一加油地点，那么我们应该在之前进行加油。我们要想次数最少，那么我们可定选择之前某个Bi最大的进行加油，全部加上，如果还不够，就选择次大的！如此直到油量能够支持卡车到下一加油站。那么我们考虑优先队列，假设目前车的油量还够，那么我们就记录当前位置跟油量，并Bi压入que中，然后如果在后面油量不够了，我们就需要从队列中每次取出之前能加最大油量的那个加油站，然后加油，如果队列是空的，说明没有加油站可以加油了，直接输出-1，否则，油量 + Bi，然后从队列弹出当前元素。很有意思的一个题目呢！！！
#include<bits/stdc++.h>
#define maxn 200004
using namespace std;
int l,p,n;
int a[maxn],b[maxn];//距离起点的距离跟最多加油量
void solve(){
a[n] = l;//为了方便起见，我们把终点也设为加油站。
b[n] = 0;
n++;
priority_queue<int> que;
int ans=0,pos = 0,tank = p;//分别表示加油次数，所在位置，油箱中汽油的量。
for(int i=0;i<n;i++){
int d = a[i] - pos;
while(tank - d < 0){
if(que.empty()){
puts("-1");
return ;
}
tank += que.top();
que.pop();
ans++;
}
tank -= d;
pos = a[i];
que.push(b[i]);
}
cout<<ans<<endl;
}
int main(){
cin>>n>>l>>p;//n表示加油站数量，l表示行驶长度，p表示车上油
for(int i=0;i<n;i++){
cin>>a[i];
}
for(int i=0;i<n;i++){
cin>>b[i];
}
solve();
return 0;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-09-11 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读