丛林探险问题

一 问题描述

一群人开着一辆卡车冒险进入丛林深处，卡车油箱坏了，每走 1 米就会漏 1 升油，他们需要到最近的城镇修理卡车。卡车当前位置和城镇之间有 N 个加油站，每个加油站都可以加油 1 到 100 升。卡车油箱容量没有限制，目前卡车距离城镇 L 米，有 P 升油。他们希望在前往城镇的路上尽可能少地停下加油，请给出到达城镇所需的最少加油次数。

二 输入和输出

1 输入

第 1 行包含单个整数N，表示加油站的数量。第 2 到 N+1 行，每行都包含两个整数，用于描述加油站，第一个整数是从城镇到加油站的距离，第二个整数是该加油站的可用油量。第 N+2 行，每行都包含两个整数 L 和 P。

2 输出

输出到达城镇所需的最少加油次数，若无法到达城镇，则输出-1。

三 输入和输出样例

1 输入样例

4

4 4

5 2

11 5

15 10

25 10

2 输出样例

2

四 分析和设计

若在可以到达的距离范围内有多个加油站，则将这些站点的加油量入队（优先队列），若走到下一个加油站之前油会耗尽，则需要加油（优先队列中最大加油量）后继续走。当油量大于或等于卡车到城镇的距离 L 时 结束。

五 图解

在输入样例中，卡车距离城镇 25 米，有 10 升油。沿着这条路，距离城镇 4、5、11 和 15 米有 4 个加油站（可求出这些加油站距离卡车 21、20、14、10 米），这些加油站可分别提供多达 4、2、5、10 升的油。

求解的过程：因为卡车有 10 升油，所以首先开车 10 米，在第 1 个加油站加油 10 升，在第 2 个加油站加油 5 升，油箱的油量累计可到达距离 25，可直接开车到镇上。答案：停靠 2 次。

六 算法设计

1 按照距离降序排序。

2 初始化。加油次数 ans =0，当前可到达的位置 pos=P，第 k 个站点 k=0。

3 若 pos < L，则执行第 4 步；否则结束，输出答案。

4 若可到达的位置超过第 k 个加油站，则将第 k 个站点的加油量入队（最大值优先），k++，一直循环到不满足条件为止。

5 若队列为空，则输出 -1，否则加油（pos+=que.top();que.pop;ans++），转向第 3 步。

七 代码

package com.platform.modules.alg.alglib.poj2431;import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;public class Poj2431 {class MyComparator implements Comparator<Integer> {public int compare(Integer num1, Integer num2) {return num2.compareTo(num1);}}public String output = "";private final int N = 10005;int n, L, P;private node port[] = new node[N];public Poj2431() {for (int i = 0; i < port.length; i++) {port[i] = new node();}}void solve() {PriorityQueue<Integer> que = new PriorityQueue<>(new MyComparator());// ans:加油次数 pos:当前可到达的位置 k:第 k 个加油站int ans = 0, pos = P, k = 0;while (pos < L) {while (pos >= L - port[k].dis && k < n) {que.add(port[k].add);k++;}if (que.isEmpty()) {output = "-1";return;} else {pos += que.poll();ans++;}}output = "" + ans;}public String cal(String input) {String[] line = input.split("\n");n = Integer.parseInt(line[0]);for (int i = 1; i <= n; i++) {String[] nums = line[i].split(" ");port[i].dis = Integer.parseInt(nums[0]);port[i].add = Integer.parseInt(nums[1]);}String[] num = line[n + 1].split(" ");L = Integer.parseInt(num[0]);P = Integer.parseInt(num[1]);Arrays.sort(port);solve();return output;}
}class node implements Comparable {public int dis; // 距离public int add; // 可加油量// 按距离降序@Overridepublic int compareTo(java.lang.Object o) {return this.dis > ((node) o).dis ? -1 : 1;}
}

八 测试

丛林探险问题

一 问题描述

一群人开着一辆卡车冒险进入丛林深处，卡车油箱坏了，每走 1 米就会漏 1 升油，他们需要到最近的城镇修理卡车。卡车当前位置和城镇之间有 N 个加油站，每个加油站都可以加油 1 到 100 升。卡车油箱容量没有限制，目前卡车距离城镇 L 米，有 P 升油。他们希望在前往城镇的路上尽可能少地停下加油，请给出到达城镇所需的最少加油次数。

二 输入和输出

1 输入

第 1 行包含单个整数N，表示加油站的数量。第 2 到 N+1 行，每行都包含两个整数，用于描述加油站，第一个整数是从城镇到加油站的距离，第二个整数是该加油站的可用油量。第 N+2 行，每行都包含两个整数 L 和 P。

2 输出

输出到达城镇所需的最少加油次数，若无法到达城镇，则输出-1。

三 输入和输出样例

1 输入样例

4

4 4

5 2

11 5

15 10

25 10

2 输出样例

2

四 分析和设计

若在可以到达的距离范围内有多个加油站，则将这些站点的加油量入队（优先队列），若走到下一个加油站之前油会耗尽，则需要加油（优先队列中最大加油量）后继续走。当油量大于或等于卡车到城镇的距离 L 时 结束。

五 图解

在输入样例中，卡车距离城镇 25 米，有 10 升油。沿着这条路，距离城镇 4、5、11 和 15 米有 4 个加油站（可求出这些加油站距离卡车 21、20、14、10 米），这些加油站可分别提供多达 4、2、5、10 升的油。

求解的过程：因为卡车有 10 升油，所以首先开车 10 米，在第 1 个加油站加油 10 升，在第 2 个加油站加油 5 升，油箱的油量累计可到达距离 25，可直接开车到镇上。答案：停靠 2 次。

六 算法设计

1 按照距离降序排序。

2 初始化。加油次数 ans =0，当前可到达的位置 pos=P，第 k 个站点 k=0。

3 若 pos < L，则执行第 4 步；否则结束，输出答案。

4 若可到达的位置超过第 k 个加油站，则将第 k 个站点的加油量入队（最大值优先），k++，一直循环到不满足条件为止。

5 若队列为空，则输出 -1，否则加油（pos+=que.top();que.pop;ans++），转向第 3 步。

七 代码

package com.platform.modules.alg.alglib.poj2431;import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;public class Poj2431 {class MyComparator implements Comparator<Integer> {public int compare(Integer num1, Integer num2) {return num2.compareTo(num1);}}public String output = "";private final int N = 10005;int n, L, P;private node port[] = new node[N];public Poj2431() {for (int i = 0; i < port.length; i++) {port[i] = new node();}}void solve() {PriorityQueue<Integer> que = new PriorityQueue<>(new MyComparator());// ans:加油次数 pos:当前可到达的位置 k:第 k 个加油站int ans = 0, pos = P, k = 0;while (pos < L) {while (pos >= L - port[k].dis && k < n) {que.add(port[k].add);k++;}if (que.isEmpty()) {output = "-1";return;} else {pos += que.poll();ans++;}}output = "" + ans;}public String cal(String input) {String[] line = input.split("\n");n = Integer.parseInt(line[0]);for (int i = 1; i <= n; i++) {String[] nums = line[i].split(" ");port[i].dis = Integer.parseInt(nums[0]);port[i].add = Integer.parseInt(nums[1]);}String[] num = line[n + 1].split(" ");L = Integer.parseInt(num[0]);P = Integer.parseInt(num[1]);Arrays.sort(port);solve();return output;}
}class node implements Comparable {public int dis; // 距离public int add; // 可加油量// 按距离降序@Overridepublic int compareTo(java.lang.Object o) {return this.dis > ((node) o).dis ? -1 : 1;}
}

八 测试