題意：你需要駕駛一輛卡車行駛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;
} 複制