旅行家的预算（JAVA）

解题思路:代码都有注释，看注释应该会懂

注意事项:

参考代码:

import java.util.Arrays;
import java.util.Scanner;


public class Main01 {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner scanner=new Scanner(System.in);
        double d1=scanner.nextDouble();//二个城市之间的距离
        double c=scanner.nextDouble();//油箱的容量
        double d2=scanner.nextDouble();//每升汽油能行驶的距离
        double p=scanner.nextDouble();//汽油价格
        int n=scanner.nextInt();
        //油价是arr[i][1];
        //距离是arr[i][0];
        double [][]arr=new double[n+1][2];
        arr[0][0]=0;
        arr[0][1]=p;
        for (int i = 1; i < arr.length; i++) {
            arr[i][0]=scanner.nextDouble();
            arr[i][1]=scanner.nextDouble();
        }
        //到达每一站需要多少距离；
        for (int i = 0; i < arr.length; i++) {
            //不等于n也就是要前面的距离减去后面的距离=需要行驶的距离；
            if (i!=n) {
                arr[i][0]=arr[i+1][0]-arr[i][0];
            }
            //如果是最后一站，那么就是终点减去这一战的距离=需要行驶的距离；
            else {
                arr[i][0]=d1-arr[i][0];
            }
        }
        //跑不到下一个加油点
         double money=0;//油钱
        double maxcm=c*d2;//一次加满油的最大距离
        for (int i = 0; i < arr.length; i++) {
            //能不能跑到每一个加油站
            if (arr[i][0]>maxcm) {
                System.out.println("No Solution");
                return;
            }
            
        }
        //如果没有加油站
        if (n==0) {
            money=(d1/d2)*p;
           System.out.println(String.format("%.2f", money));
            return;
        }
        //现在要判断哪一个加油站最便宜，但是第一站是必须要加油的，
        //先找到那一站比第一站便宜，如过没有找到，那就把油加满，看最大距离能跑到那一战，所以在找的同时把距离加上
        //要是第一站最贵，那就少加一点，到下一站加
        //要是第一站最便宜就多加点，加到能到达n个站后，在n个站加
        double sen=0;//油箱剩余的油
        int i=0; //这个是初始加油站，一个不变的值，除非j给到i；
        double sumju=0; //汽车一共行驶的距离
        while (i<n) {
            double ju=0;//车子行驶的距离
            //找每一站的油，看那一战比第一站还要便宜
            //如果第一站没有找到，那么就加上第一站的距离，找下一站，一直找，
            //直到每一站的距离总和>最大距离，那就不找了，j就减去一站，然后减去距离，只能在j站加油，
            //要是找到了，比第一站还要便宜的油价，那么j就是第j站最便宜
            int j;
            for (j = i+1; j <=n;j++) {
                //先加上每一段路的距离和车子行驶的总距离
                ju+=arr[j-1][0];
                sumju+=arr[j-1][0];
                //首先判断那一站油钱最便宜，到了最便宜的油站，那么油钱只算起点到这一战的钱，
                if (arr[i][1]>=arr[j][1]) {
                    //算起点到找到j油站的油钱
                    money+=ju/d2*arr[i][1];
                    //那么此时油箱就为0；
                    sen=0;
                    //如果最便宜的那一站刚刚好是最后一战，那么久算出最后一战的到终点的价钱；
                    if (n==j) {
                        money+=((d1-sumju)/d2-sen)*arr[j][1];
                    }
                    break;
                }
                //接着判断是不是最后一战，怕他是最后一站，但是油钱是起点站最便宜，而最大距离也能到达终点，（之前判定过便宜油价了）
                if (j==n) {
                    //要是最后一战就加上最后一个加油站到终点的距离，然后进行判断能不能到
                    ju+=d1-sumju;
                    //不能到，就算出之前的钱+最后一战到终点的钱
                    if (ju>maxcm) {
                        //到最后一战的距离
                        ju=ju-(d1-sumju);
                        money+=(c-sen)*arr[i][1];
                        sen=c-(ju/d2);
                        money+=((d1-sumju)/d2-sen)*arr[j][1];
                        break;
                        
                    }
                    //能到，那么就直接算出起始站到终点站的钱
                    else {
                        money+=ju/d2*arr[i][1];
                        sen=0;
                        break;
                    }
                    
                }
                //判断一直找不到加油站，但是最大距离到不了终点的情况，那就j-1，距离减去一开始加的距离
                if (maxcm<ju) {
                    j-=1;
                    ju-=arr[j-1][0];
                    money+=(c-sen)*arr[i][1];
                    sen=c-maxcm/d2;
                    break;
                }
            }
            //接着把汽车行驶的站给到起始站；
            i=j;
        }
        System.out.println(String.format("%.2f", money));

    }

}