Expedition(优先队列)

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("加油站加油)");
	}
}
========================================Talk is cheap, show me the code=======================================