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=======================================
Expedition(优先队列)
CSDN博客地址:https://blog.csdn.net/qq_34115899