题目
Problem description
一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离D1、汽车油箱的容量C（以升为单位）．每升汽油能行驶的距离D2、出发点每升汽油价格P和沿途油站数N（N可以为零），油站i离出发点的距Di、每升汽油价格 Pi（ i＝l，2，...N）。计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“-1”。
Input
输入数据的第一行是四个实数；
D1 C D2 P分别表示两个城市之间的距离，汽车油箱的容量，每升汽油能行驶的距离，出发点每升汽油格；
第二行是一个整数N,沿途的油站数。
第三行到第N+2，每一行是一个油站的基本信息描述，包括该油站离出发点的距离，该油站每升汽油的格。 Output
输出到达目的城市的最小费用(四舍五入到两位小数)，若不能到达目的城市则输出 -1
Sample Input
275.6 11.9 27.4 2.8
2
102.0 2.9
220.0 2.2 Sample Output
26.95Problem Source
// 测试用例
275.6 11.9 17.4 2.8
2
102.0 2.9
220.0 2.21
42.54//
275.6 11.9 10.4 2.8
3
102.0 2.1
160.2 2.3
220.0 2.2
62.99分析：
哨兵单元往往能够简化逻辑，减少判断和边界处理。在这道题中尤为明显。
我们把出发点当做距离为0，油价为p和普通油站放在一起；把目的地当做距离为s，油价为-1的油站跟普通油站放在一起。这样就得到了一个包含n+2个油站的数组。问题变得更加清楚简洁。
假如当前在第i个油站，那么唯一需要考虑的就是在这个油站需要加多少油。
这就需要考虑后面的油站：我只需要尽量保证我的油能够到达下一个比较便宜的油站即可。如果无法到达下一个便宜油站，那么我就需要加满油；如果我加满油依然无法到达下一个便宜的油站，那么我仍然需要加满油。
而经过“哨兵单元”处理，我们把目的地当做一个距离为s，油价为-1的油站放进了油站数组里面，所以我们一定能够找到下一个便宜的油站。这样就简化了逻辑。
如果潦草地写，这道题复杂度为$O(N^2)$，利用单调栈从左往右初始化每个元素的右面较小值，可以实现O(N)复杂度。
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;public class Main {
class Point {double dis, price;Point(double dis, double price) {this.dis = dis;this.price = price;}
}Main() {Scanner cin = new Scanner(System.in);double s = cin.nextDouble(), c = cin.nextDouble(), d = cin.nextDouble(), p = cin.nextDouble();int n = cin.nextInt();Point[] a = new Point[n + 2];for (int i = 0; i < n; i++) a[i] = new Point(cin.nextDouble(), cin.nextDouble());a[n] = new Point(0, p);a[n + 1] = new Point(s, -1);//终点的油是免费的Arrays.sort(a, Comparator.comparing(x -> x.dis));double money = 0, oil = 0, lastPos = 0;for (int i = 0; i < a.length; i++) {oil -= (a[i].dis - lastPos) / d;//剩余的油量if (oil < 0) {money = -1;break;}if (a[i].price < 0) break;int j = i + 1;for (; j < a.length; j++) {if (a[j].price < a[i].price) break;}double dis = a[j].dis - a[i].dis;double need = dis / d;//到达下一站需要的油量need = Math.min(c, need);double add = need - oil;//现在需要加的油量if (add > 0) {money += add * a[i].price;oil += add;}lastPos = a[i].dis;}if (money == -1) System.out.println(-1);else {long x = Math.round(money * 100);System.out.println(x / 100 + "." + x % 100);}
}public static void main(String[] args) {new Main();
}
}
