目录
一、问题描述
二、分析过程
三、参考代码及运行结果
一、问题描述
二、分析过程
i ：第i个加油站 i = 0：出发地i = k：目的地（共 k+1 个站，由问题知，k = 5）x[i] ：第 i 站到 i+1 站的距离，由问题知，需定义int x[5]，且x[0] = 30，x[1] = 40，...，x[4] = 50。n ：加满油行驶的最远距离，由问题知，n = 90。count：一共的加油次数贪心策略：每次开到尽量远的加油站加油，也就是说不得不加油的时候。如：到了一个加油站正好没油，或者到了一个加油站不加油，剩余油就不够开到下一个加油站。三、参考代码及运行结果
public class Car {public static void greedy(int x[], int n ,int k){// 检查每相邻两个加油站的距离不超过 n，否则无解for(int i=0; i<k; i++)if(x[i] > n){System.out.println("No solution");return ;}// 一切正常，开始算法int count = 1; // 一共所需加油的次数，出发时必须加油一次System.out.println("需要在第 0 个加油站加油一次");int distance = 0;// 保存 一次可能最长行驶的距离，累加相邻距离，直到 > nfor(int i=0; i<k; i++){distance += x[i]; // 累加 x[0]~x[i] ，即一次可能最长行驶的距离if(distance > n){ // 直到加上x[i]时 一次可能最长行驶的距离 > n (不加x[i]时，<= n，即中途不用加油)count++;// 加一次油distance=x[i];// 以当前 x[i] 为起始点，重新计算distance 一次可能的最长行驶的距离System.out.printf("需要在第 %d 个加油站加油一次\n", i);}}System.out.printf("一共需要加油的总次数： %d 次\n", count);}public static void main(String[] args) {int[] x = {30,40,80,12,50};// 初始化 相邻站的距离int k = 5; // 一共的站点数，算上出发站，目的站int n = 90; // 加一次油最长行驶的距离greedy(x, n ,k);// 调用算法，计算最少的加油次数}}
