To Fill Or Not To Fill题解——贪心策略（Java题解）

贪心策略Java版

1.添加终点加油站（路程，0）。0表示价格为0。
2.先将所有加油站按照距离远近排序，距离相同则按照价格从低到高排序。
3.从index = 1开始寻找比当前加油站（index = 0）处价格低的最近加油站（这些加油站必须在油箱加满后能开车到达的距离内），找到一个最近的，则将油加到正好开车到价格低的加油站所需油量。计算花费，车开到加油站油量耗尽。更新index、当前距离currentDist、当前加油站价格currentCost。
4.如果在index = 1处，在能到达的范围内没有比当前价格更低的加油站，那改变策略：寻找能到达的所有加油站中价格最低但是比当前价格高的加油站，接着在当前加油站加满油，开车过去。此时剩余油量remain为capacity-路程所需油量。计算花费，更新index、currentDist、currentCost。
5.重复步骤3-4，直到布尔变量way==false，加满油也无法到达下一加油站。或者currentDist==dist（终点）。退出循环。
6.布尔变量less代表是否找到步骤3中描述的价格较低的加油站。
7.compare方法的重写：返回-1表示后面的值（o2）与前面的值（o1）需要互换位置。返回0和1则不用。
这个思路我觉得是比较好的，易于理解，我理解了思路后用Java重写的算法。参考的文章是用C++写的，大家都用C++，看来我以后也得学C++了。
参考思路链接：https://blog.csdn.net/RPG_Zero/article/details/100598669

import java.util.*;
public class Main {

    public static void main(String[] args) {
        go();

    }

//    15 2383 13 10
//    424238335 0
//    86 60
//    49 161
//    62 1033
//    90 1279
//    63 1891
//    40 311
//    72 13
//    11 1945
//    67 1095

    public static void go() {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int capacity = in.nextInt();
            int dist = in.nextInt();
            int efit = in.nextInt();
            int n = in.nextInt();
            ArrayList list = new ArrayList();
            for (int i = 0; i < n; i++) {
                list.add(new Station(in.nextDouble(), in.nextInt()));
            }
            list.add(new Station(0, dist));
// 加油站排序
            Collections.sort(list, new Comparator() {
                public int compare(Station o1, Station o2) {
                    if (o1.dist < o2.dist) {
                        return -1;
                    }else if (o1.dist > o2.dist){
                        return 1;
                    }else {
                        if (o1.price < o2.price) {
                            return -1;
                        }else {
                            return 1;
                        }
                    }
                }
            });
// 如果排序后第一个加油站都无法到达，此处我直接return了，但是按理来讲应该设置next为true然后break进行下一个用例计算。
            if (list.get(0).dist != 0) {
                return;
            }
            double totalCost = 0;
            int currentDist = 0;
            double currentCost = list.get(0).price;
            int index = 1;
            int max = capacity * efit;
            double remain = 0;
            boolean next = false;
// 外层循环记录每一次判断汽车是否能够开往下一个加油站
            while (currentDist < dist) {
                boolean way = false;
                boolean less = false;
// 第一个for循环寻找是否有比当前价格便宜的最近加油站
                for (int i = index; i <= n; i++) {
                    Station temp = list.get(i);
                    if (max + currentDist >= temp.dist) {
                        way = true;
                        if (currentCost >= temp.price) {
                            less = true;
                            index = i;
                            break;
                        }
                    }else {
                        break;
                    }
                }
// 不能到达下一个加油站，输出最大行驶距离，进行下一个用例
                if (!way) {
                    System.out.printf("The maximum travel distance = %.2f", currentDist + (capacity - remain) * efit);
                    System.out.println();
                    next = true;
                    break;
                }
// 找到了价格更低的加油站，加刚好满足距离要求的***驶过去。
                if (less) {
                    Station s = list.get(index);
                    int len = s.dist - currentDist;
                    double need = (double)len / efit;
                    if (need >= remain) {
                        totalCost += (need - remain) * currentCost;
                        remain = 0;
                    }else {
                        remain -= need;
                    }
                    currentDist = s.dist;
                    currentCost = s.price;
                    index++;
                }else {// 没找到价格更低的加油站，找价格高一些的最便宜加油站，行驶过去。
                    double minCost = Double.MAX_VALUE;
                    for (int j = index; j <= n; j++) {
                        Station temp = list.get(j);
                        if (max + currentDist >= temp.dist) {
                            if (minCost > temp.price) {
                                index = j;
                                minCost = temp.price;
                            }
                        }else {
                            break;
                        }
                    }
                    Station s = list.get(index);
                    int len = s.dist - currentDist;
                    double need = (double)len / efit;
                    totalCost += (capacity - remain) * currentCost;
                    remain = capacity - need;
                    currentDist = s.dist;
                    currentCost = s.price;
                    index++;
                }
            }
// 到达不了重点，进行下一个用例
            if (next) {
                continue;
            }
// 到达重点，输出总花费
            System.out.printf("%.2f", totalCost);

        }

    }
}
class Station{
    public double price;
    public int dist;
    public Station(double price, int dist) {
        super();
        this.price = price;
        this.dist = dist;
    }

}