一輛汽車加滿油后可行駛n公里。旅途中有若干個加油站。設計一個有效算法，指出應在哪些加油站停靠加油，使沿途加油次數最少。對于給定的n(n <= 5000)和k(k <= 1000)個加油站位置，編程計算最少加油次數。并證明算法能產生一個最優解。
要求：
輸入：第一行有2個正整數n和k，表示汽車加滿油后可行駛n公里，且旅途中有k個加油站。接下來的1 行中，有k+1 個整數，表示第k個加油站與第k-1 個加油站之間的距離。第0 個加油站表示出發地，汽車已加滿油。第k+1 個加油站表示目的地。
輸出：輸出編程計算出的最少加油次數。如果無法到達目的地，則輸出”NoSolution”。

思路：
汽車行駛過程中，應走到自己能走到并且離自己最遠的那個加油站，在那個加油站加油后再按照同樣的方法貪心

具體算法：
先檢測各加油站之間的距離，若發現其中有一個距離大于汽車加滿油能跑的距離，則輸出no solution。否則，對加油站間的距離進行逐個掃描，盡量選擇往遠處走，不能走了就讓num++，最終統計出來的num便是最少的加油站數

#include <iostream>using namespace std;void greedy(int d[],int n,int k) {int num = 0;for(int i = 0;i <= k;i++) { //先判斷是否都能到達if(d[i] > n) {cout<<("no solution\n");return;}}for(int i = 0,s = 0;i <= k;i++) {s += d[i];if(s > n) {num++;s = d[i];}}cout<<num; }int main() {int i,n,k;int d[1000];cin>>n>>k;for(i=0;i=k;i++){cin>>d[i];}greedy(d,n,k);cout << "Hello world!" << endl;return 0; }

總結

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

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