代码语言：javascript复制
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
/**
* Expedition 你需要驾驶一辆卡车行驶L单位距离。最开始时，卡车上有P单位的汽油。卡车上每开1单位距离需要消耗1单位的汽油。
* 如果在途中车上的汽油耗尽，卡车就无法继续前行，因而无法到达终点。在途中一共有N个加油站。
* 第i个加油站在距离起点Ai单位的地方，最多可以给卡车加Bi单位汽油。 假设卡车的燃料箱的容量是无限大的，无论加多少油都没有问题。那么请问卡车能否到达终点？
* 如果可以，最少需要加多少次油？如果可以到达终点，输出最少的加油次数，否则输出-1。 限制条件 1≤N≤10000
* 1≤L≤1000000，1≤P≤1000000 1≤Ai<L, 1≤Bi≤100
*
* 测试数据 输入： N = 4, L = 25, P = 10 A = {10, 14, 20, 21} B = {10, 5, 2, 4} 输出：
* 2(在第一个和第二个加油站加油)
*
* @author lcy
*
*/
public class Expedition {
static final int MAX_N = 1000000;
static int L, P, N, j;
static int[] A = new int[MAX_N 1], B = new int[MAX_N 1];
static int[] count = new int[MAX_N 1];
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
N = cin.nextInt();
L = cin.nextInt();
P = cin.nextInt();
for (int i = 0; i < N; i) {
A[i] = cin.nextInt();
}
for (int i = 0; i < N; i) {
B[i] = cin.nextInt();
}
solve();
cin.close();
}
public static void solve() {
// 为了写起来方便，我们把终点也认为是加油站
A[N] = L;
// 最后终点看成加油站，加油量为0
B[N] = 0;
Comparator<Integer> order = new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
};
Queue<Integer> q = new PriorityQueue<Integer>(N, order);
// ans：加油次数 pos：现在所在位置 tank：油箱中汽油的量
int ans = 0, pos = 0, tank = P;
for (int i = 0; i <= N; i) {
// 接下来要前进的距离
int d = A[i] - pos;
while (tank - d < 0) {
if (q.isEmpty()) {
System.out.println("-1");
return;
}
tank = q.peek();
// 记录加油的地方,扫一遍B数组，因为无序,输出字典序加油站的地方
// 初始P=15, L=20
// A===>8, 10, 15(加的油算第2个加油站加的，而不是第3个，按字典序)
// B===>2, 5, 5
int temp = q.poll();
for (int t = 0; t < N; t) {
if (temp == B[t]) {
count[j ] = t 1;
break;
}
}
ans;
}
tank -= d;
pos = A[i];
q.add(B[i]);
}
System.out.print(ans);
System.out.print("(在");
for (int i = 0; i < j; i) {
System.out.print("第" count[i] "个");
}
System.out.println("加油站加油)");
}
}
