POJ - 1700 Crossing River

题目来源

1700 -- Crossing River (poj.org)

题目描述

有N个人想要过河，但是只有一艘船，并且这艘船最多只能搭载两个人。

现在需要你制定某种策略，花费最少的时间，让所有人渡河。

注：每个人的划船速度不同，当两个人划船时，过河时间取决于耗时最长的那个人。

输入描述

第一行输入一个整数T（1 ≤ T ≤ 20），表示有T组测试用例。

接下来输入T组用例，每组用例有两行：

• 第一行输入一个整数N（N <= 1000），表示有N个人需要过河。
• 第二行输入N个整数，以空格隔开，每个整数代表一个人的过河时间。注：每个人的过河时间都不会超过100秒。

输出描述

针对每组测试用例，输出一行，输出内容为：该组用例中所有人过河所需的最短时间。

用例

题目解析

本题是经典的贪心算法题。

假设所有人过河时间保存在time数组中（time.length = n），首先将time数组升序，那么第 0 个人的过河时间最短，即最快的人，第 n-1 个人的过河时间最长，即最慢的人。

如果想花费最少的时间让所有人过河，此时有两种最佳策略：

• 策略一：

1. 首先让本岸最快的两个人，即0，1过河，此轮耗时 time[1]
2. 然后让对岸最快的人划船回来，即0划船回来，此轮耗时time[0]
3. 之后让本岸最慢的两人划船过河，即n-1，n-2划船过河，此轮耗时time[n-1]
4. 最后让对岸最快的人划船回来，即1划船回来，此轮耗时time[1]

这种策略运两个最慢的人过河，花费时间为：time[1] + time[0] + time[n-1] + time[1]

• 策略二：

1. 首先让本岸最快的和最慢的过河，即0，n-1过河，此轮耗时 time[n-1]
2. 然后让对岸对岸最快的划船回来，即0划船回来，此轮耗时 time[0]
3. 之后让本岸最快的和最慢的过河，即0，n-2过河，此轮耗时 time[n-2]
4. 然后让对岸最快的划船回来，即0划船回来，此轮耗时 time[0]

这种策略运两个最慢的人过河，花费时间为：time[n-1] + time[0] + time[n-2] + time[0] 

其他策略花费的时间都将大于等于这两个策略，大家可以自己尝试一下。

可能大家会有疑问，为什么上面策略，需要以运两个最慢的人举例呢？

首先，“两个”是因为船最多只能载两人，

其次，“最慢”是因为：

让最慢的两个人所浪费的时间最小化，这可以通过让他们一起过桥来实现。

具体原因可以看下：中文配音TED烧脑谜题 - 四人过桥 - 第一季01_哔哩哔哩_bilibili

该视频中的策略其实就是上面的策略一：

让最慢的两个人所浪费的时间最小化，这可以通过让他们一起过桥来实现，

因为需要有人提着灯（开船）返回，所以得让速度最快得两个人来完成这个任务。

因此，本题的理论最佳策略就是：策略一。但是，有时候策略二也会比策略一更优：

比如当：2 * time[1] <  + time[0] + time[n-2] 时

好了，关于为啥总是优先运两个最慢的人过河的原因的解释说明，到此结束。下面我们开始运人：

总人数为n，每次运两个最慢的人过河，那么 n -= 2 就需要不断进行，但是当 n <= 3 时，其实此时不需要再纠结上面两种策略了。

• 当 n == 1时，此时必然剩下的是最快的那个人，因为我们优先将最慢地两个人运到对岸，那么最后本岸剩下一个人时，必然是最快的那个人，因此最后一个过河耗时就是time[0]
• 当 n == 2时，此时必然剩下的是最快的两个人，即0和1，此时过河耗时为time[1]
• 当 n == 3时，此时必然剩下的是最快的三个人，即0,1,2，此时过河耗时采用上面两种策略的会产生相同运输方案：即首先0，1过河（cost += time[1]），然后0回来（cost += time[0]），最后0，2过河（cost += time[2]）

JavaScript算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");const rl = readline.createInterface({input: process.stdin,output: process.stdout,
});const lines = [];
// 一共T组测试用例
let t;
rl.on("line", (line) => {lines.push(line);if (lines.length == 1) {t = lines[0] - 0;}if (t && lines.length == t * 2 + 1) {lines.shift();while (lines.length > 0) {// 每组测试用例有n个整数，代表n个人const n = lines.shift() - 0;// t数组记录每个人的过河时间const t = lines.shift().split(" ").map(Number);// 打印当前用例所有人过河所需的最短时间console.log(getMinCrossRiverTime(n, t));}}
});function getMinCrossRiverTime(n, t) {// 所有人过河所需的最短用时costlet cost = 0;while (n > 0) {if (n == 1) {// 如果只剩一个人，那肯定是t[0]，即最快的那个人，过河耗时t[0]cost += t[0];break;} else if (n == 2) {// 如果只剩两个人，那肯定是t[0],t[1]，即最快的两个人，过河耗时t[1]cost += t[1];break;} else if (n == 3) {// 如果只剩三个人，那肯定是t[0],t[1],t[2]，即最快的三个人，此时我们可以让t[0],t[1]过河，cost+=t[1]，然后t[0]划船回来，cost+=t[0]，最后t[0],t[2]过河，cost+=t[2]cost += t[1] + t[0] + t[2];break;} else {// 如果剩余人数超过三个，那么此时有两种过河策略：/*1、首先让t[0],t[n-1]过河，耗时cost += t[n-1]，然后t[0]划船回来，cost += t[0]，再然后t[0],t[n-2]过河，耗时cost += t[n-2]，然后t[0]划船回来，cost+=t[0]即此方案总耗时 = t[n-1] + t[0] + t[n-2] + t[0]2、首先t[0],t[1]划船过河，耗时cost += t[1]，然后t[0]划船回来，cost += t[0]，再然后最慢的两个人一起过河t[n-1]，t[n-2]过河，耗时cost += t[n-1]，最后t[1]划船回来，耗时cost += t[1]即此方案总耗时 = t[1] + t[0] + t[n - 1] + t[1]*/cost += Math.min(t[n - 1] + t[0] + t[n - 2] + t[0],t[1] + t[0] + t[n - 1] + t[1]);// 把最慢的两个人运到了对岸，因此本岸人数减2n -= 2;}}return cost;
}

Java算法源码

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);// 一共T组测试用例int T = sc.nextInt();for (int i = 0; i < T; i++) {// 每组测试用例有n个整数，代表n个人int n = sc.nextInt();// t数组记录每个人的过河时间int[] t = new int[n];for (int j = 0; j < n; j++) {t[j] = sc.nextInt();}// 打印当前用例所有人过河所需的最短时间System.out.println(getMinCrossRiverTime(n, t));}}public static int getMinCrossRiverTime(int n, int[] t) {// 所有人过河所需的最短用时costint cost = 0;while (n > 0) {if (n == 1) {// 如果只剩一个人，那肯定是t[0]，即最快的那个人，过河耗时t[0]cost += t[0];break;} else if (n == 2) {// 如果只剩两个人，那肯定是t[0],t[1]，即最快的两个人，过河耗时t[1]cost += t[1];break;} else if (n == 3) {// 如果只剩三个人，那肯定是t[0],t[1],t[2]，即最快的三个人，此时我们可以让t[0],t[1]过河，cost+=t[1]，然后t[0]划船回来，cost+=t[0]，最后t[0],t[2]过河，cost+=t[2]cost += t[1] + t[0] + t[2];break;} else {// 如果剩余人数超过三个，那么此时有两种过河策略：/*1、首先让t[0],t[n-1]过河，耗时cost += t[n-1]，然后t[0]划船回来，cost += t[0]，再然后t[0],t[n-2]过河，耗时cost += t[n-2]，然后t[0]划船回来，cost+=t[0]即此方案总耗时 = t[n-1] + t[0] + t[n-2] + t[0]2、首先t[0],t[1]划船过河，耗时cost += t[1]，然后t[0]划船回来，cost += t[0]，再然后最慢的两个人一起过河t[n-1]，t[n-2]过河，耗时cost += t[n-1]，最后t[1]划船回来，耗时cost += t[1]即此方案总耗时 = t[1] + t[0] + t[n - 1] + t[1]*/cost += Math.min(t[n - 1] + t[0] + t[n - 2] + t[0], t[1] + t[0] + t[n - 1] + t[1]);// 把最慢的两个人运到了对岸，因此本岸人数减2n -= 2;}}return cost;}
}

Python算法源码

# 算法逻辑
def getMinCrossRiverTime(n, t):# 所有人过河所需的最短用时costcost = 0while n > 0:if n == 1:# 如果只剩一个人，那肯定是t[0]，即最快的那个人，过河耗时t[0]cost += t[0]breakelif n == 2:# 如果只剩两个人，那肯定是t[0],t[1]，即最快的两个人，过河耗时t[1]cost += t[1]breakelif n == 3:# 如果只剩三个人，那肯定是t[0],t[1],t[2]，即最快的三个人，此时我们可以让t[0],t[1]过河，cost+=t[1]，然后t[0]划船回来，cost+=t[0]，最后t[0],t[2]过河，cost+=t[2]cost += t[1] + t[0] + t[2]else:# 如果剩余人数超过三个，那么此时有两种过河策略："""1、首先让t[0],t[n-1]过河，耗时cost += t[n-1]，然后t[0]划船回来，cost += t[0]，再然后t[0],t[n-2]过河，耗时cost += t[n-2]，然后t[0]划船回来，cost+=t[0]即此方案总耗时 = t[n-1] + t[0] + t[n-2] + t[0]2、首先t[0],t[1]划船过河，耗时cost += t[1]，然后t[0]划船回来，cost += t[0]，再然后最慢的两个人一起过河t[n-1]，t[n-2]过河，耗时cost += t[n-1]，最后t[1]划船回来，耗时cost += t[1]即此方案总耗时 = t[1] + t[0] + t[n - 1] + t[1]"""cost += min(t[n - 1] + t[0] + t[n - 2] + t[0], t[1] + t[0] + t[n - 1] + t[1])# 把最慢的两个人运到了对岸，因此本岸人数减2n -= 2return cost# 输入获取
T = int(input())for _ in range(T):n = int(input())t = list(map(int, input().split()))# 算法调用print(getMinCrossRiverTime(n, t))