汽車從起點(diǎn)出發(fā)駛向目的地，該目的地位于出發(fā)位置東面?target?英里處。

沿途有加油站，每個(gè)?station[i]?代表一個(gè)加油站，它位于出發(fā)位置東面?station[i][0]?英里處，并且有?station[i][1]?升汽油。

假設(shè)汽車油箱的容量是無限的，其中最初有?startFuel?升燃料。它每行駛 1 英里就會(huì)用掉 1 升汽油。

當(dāng)汽車到達(dá)加油站時(shí)，它可能停下來加油，將所有汽油從加油站轉(zhuǎn)移到汽車中。

為了到達(dá)目的地，汽車所必要的最低加油次數(shù)是多少？如果無法到達(dá)目的地，則返回?-1?。

注意：如果汽車到達(dá)加油站時(shí)剩余燃料為 0，它仍然可以在那里加油。如果汽車到達(dá)目的地時(shí)剩余燃料為 0，仍然認(rèn)為它已經(jīng)到達(dá)目的地。

輸入：target = 1, startFuel = 1, stations = [] 輸出：0 解釋：我們可以在不加油的情況下到達(dá)目的地。 輸入：target = 100, startFuel = 1, stations = [[10,100]] 輸出：-1 解釋：我們無法抵達(dá)目的地，甚至無法到達(dá)第一個(gè)加油站。 輸入：target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]] 輸出：2 解釋： 我們出發(fā)時(shí)有 10 升燃料。 我們開車來到距起點(diǎn) 10 英里處的加油站，消耗 10 升燃料。將汽油從 0 升加到 60 升。 然后，我們從 10 英里處的加油站開到 60 英里處的加油站（消耗 50 升燃料）， 并將汽油從 10 升加到 50 升。然后我們開車抵達(dá)目的地。 我們沿途在1兩個(gè)加油站?？?#xff0c;所以返回 2 。

一開始想的是在每次可以走的最遠(yuǎn)的路程所經(jīng)過的加油站中選擇一個(gè)油量最大的，但是忽略了可能加一次油到不了下一站，或者下下一站。因此需要循環(huán)找第二大油量，甚至第3，4，5....大的油量 #include<iostream> #include<cstdio> #include<vector> #include<cstring> using namespace std; bool vis[1000];int go(int maxdis,vector< vector<int> >& stations) {int mx=0,pos=-1,num=stations.size(),i=0;while(i<num&&stations[i][0]<=maxdis){if(stations[i][1]>mx&&!vis[i]){mx=stations[i][1];pos=i;}i++;}if(pos==-1)return -1;else{vis[pos]=1;return mx;}} int minRefuelStops(int target, int startFuel, vector< vector<int> >& stations) {memset(vis,0,sizeof(vis));//把終點(diǎn)當(dāng)作一個(gè)加油站vector<int>v;v.push_back(target);v.push_back(0);stations.push_back(v);int num=stations.size();//cout<<num<<endl;if(startFuel>=target)return 0;else{//beg是當(dāng)前加油的下標(biāo)，i是可以走到的加油站下標(biāo)int dis=startFuel,i=0,start=0,cou=0,beg=0;while(start+dis<target){//cout<<"start: "<<start<<" "<<i<<endl;//計(jì)算每次行駛完所有的汽油后可以經(jīng)過的加油站，在含油量最高的加油站處加油//cout<<stations[i][0]<<endl;int mx=0,po=-1;int maxdis=start+dis; //可以走的最遠(yuǎn)距離//找出第一個(gè)到達(dá)不了的加油站while(i<num&&stations[i][0]<=maxdis){i++;}//不斷加油直到可以走到while(i<num&&start+dis<stations[i][0]){int tmp=go(maxdis, stations);if(tmp!=-1){dis+=tmp;cou++;}elsebreak;}if(start+dis>=stations[i][0]){dis-=(stations[i][0]-start);start=stations[i][0];beg=i;}elsebreak;}if(start+dis>=target)return cou;elsereturn -1;} }int main() {vector< vector<int> > stations;int target,startFuel;while(1){scanf("%d%d",&target,&startFuel);vector<int>s;s.push_back(14);s.push_back(123);stations.push_back(s);s.clear();s.push_back(145);s.push_back(203);stations.push_back(s);s.clear();s.push_back(344);s.push_back(26);stations.push_back(s);s.clear();s.push_back(357);s.push_back(68);stations.push_back(s);s.clear();s.push_back(390);s.push_back(35);stations.push_back(s);s.clear();s.push_back(478);s.push_back(135);stations.push_back(s);s.clear();s.push_back(685);s.push_back(108);stations.push_back(s);s.clear();s.push_back(823);s.push_back(186);stations.push_back(s);s.clear();s.push_back(934);s.push_back(217);stations.push_back(s);s.clear();s.push_back(959);s.push_back(80);stations.push_back(s);printf("%d\n",minRefuelStops(target,startFuel,stations));} }

?

轉(zhuǎn)載于:https://www.cnblogs.com/flightless/p/10427756.html

總結(jié)

以上是生活随笔為你收集整理的871 最低加油次数的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。