已知一條公路上，有一個起點與一個終點，這之間有n個加油站;已知從這n個加 油站到終點的距離d與各個加油站可以加油的量l，起點位置至終點的距離L與起 始時刻油箱中汽油量P;假設使用1個單位的汽油即走1個單位的距離，油箱沒有 上限，最少加幾次油，可以從起點開至終點?(如果無法到達終點，返回-1)

這個貪心過程和跳越游戲的貪心規律十分類似，跳躍游戲：獲取最少跳躍次數，即在無法到達更遠的地方時，在這之前應該跳到一個可以到達更 遠位置的位置!

這里和跳躍游戲的差異是跳躍游戲中節點之間的距離是恒定的，而本題目中節點之間的距離卻是不定得，所以想要在初始油量的支撐下獲取可以加油的節點的過程中需要實時維護一個最大值，即節點可以加的油量（這個維護使用最大堆來維護）。

過程如下：
1.設置一個最大堆，用來存儲經過的加油站的汽油量。
2.按照從起點至終點的方向，遍歷各個加油站之間與加油站到終點距離。
3.每次需要走兩個加油站之間的距離d，如果發現汽油不夠走距離d時，從最 大堆中取出一個油量添加，直到可以足夠走距離d。
4.如果把最大堆的汽油都添加仍然不夠行進距離d，則無法達到終點。
5.當前油量P減少d。
6.將當前加油站油量添加至最大堆

實現如下：

int cmp(pair<int,int> a,pair<int,int> b) {return a.first > b.first;
}/*
L為起點到終點的距離
P起點初始的汽油容量
stop:<加油站至終點的距離，加油站汽油量>
*/
int get_least_expedition(int L, int P,vector<pair<int,int>> &stop) {priority_queue<int> Q;//維護的最大堆int result = 0;//記錄加油的次數sort(stop.begin(), stop.end(),cmp);//對加油站至終點的距離從大到小進行排序，防止輸入無序的情況stop.push_back(make_pair(0,0));//將終點的pair入數組for (int i = 0;i < stop.size(); ++i) {int dis = L - stop[i].first;/*加油的條件是堆中油量不為空且當前油量小于要行駛的距離*/while(!Q.empty() && dis > P){P += Q.top();Q.pop();result ++;}/*無法到達終點的情況是最大堆中無油可加，且當前油量不足以行駛剩余距離*/if (Q.empty() && dis > P) {return -1;}P -= dis;L = stop[i].first;Q.push(stop[i].second);}return result;
}

測試代碼如下：

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>using namespace std;int cmp(pair<int,int> a,pair<int,int> b) {return a.first > b.first;
}int get_least_expedition(int L, int P,vector<pair<int,int>> &stop) {priority_queue<int> Q;int result = 0;sort(stop.begin(), stop.end(),cmp);stop.push_back(make_pair(0,0));for (int i = 0;i < stop.size(); ++i) {int dis = L - stop[i].first;while(!Q.empty() && dis > P){P += Q.top();Q.pop();result ++;}if (Q.empty() && dis > P) {return -1;}P -= dis;L = stop[i].first;Q.push(stop[i].second);}return result;
}int main() {vector<pair<int,int>> stop;int P;int L;int distance,fuel;int N;cin >> N;for (int i = 0;i < N; ++i) {cin >> distance;cin >> fuel;stop.push_back(make_pair(distance,fuel));}cin >> L;cin >> P;cout << get_least_expedition(L,P,stop);return 0;
}

輸入輸出如下

輸入：
4
4 4
5 2
11 5
15 10
25 10
輸出：
2

總結

以上是生活随笔為你收集整理的贪心：expedition 最优加油方法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。