POJ - 1700 Crossing River

Myth丶恋晨 2023-09-26 20:03 85阅读 0赞

### 题目来源 ###

[1700 -- Crossing River (poj.org)][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][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) {
      // 所有人过河所需的最短用时cost
      let 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]
          );
          // 把最慢的两个人运到了对岸，因此本岸人数减2
          n -= 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) {
        // 所有人过河所需的最短用时cost
        int 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]);
            // 把最慢的两个人运到了对岸，因此本岸人数减2
            n -= 2;
          }
        }
    
        return cost;
      }
    }

### Python算法源码 ###

# 算法逻辑
    def getMinCrossRiverTime(n, t):
        # 所有人过河所需的最短用时cost
        cost = 0
    
        while n > 0:
            if n == 1:
                # 如果只剩一个人，那肯定是t[0]，即最快的那个人，过河耗时t[0]
                cost += t[0]
                break
            elif n == 2:
                # 如果只剩两个人，那肯定是t[0],t[1]，即最快的两个人，过河耗时t[1]
                cost += t[1]
                break
            elif 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])
                # 把最慢的两个人运到了对岸，因此本岸人数减2
                n -= 2
    
        return cost
    
    
    # 输入获取
    T = int(input())
    
    for _ in range(T):
        n = int(input())
        t = list(map(int, input().split()))
        # 算法调用
        print(getMinCrossRiverTime(n, t))

## 动态规划解法 ##

### 题目解析 ###

如果大家理解了前面的贪心算法思路，其实动态规划思路也很简单了。

首先依旧是是将渡河时间数组time升序，time.length == n。

我们定义一个dp数组，长度为n，dp\[i\]的含义是将前 i 个人（速度最快的前 i 个人）渡过河所需的最短时间。

此时我们可以从dp\[i-1\]或dp\[i-2\]推导出dp\[i\]。

*  如果前 i - 1 个人过河用时为dp\[i - 1\]

1.  现在在本岸又新增了第 i 号人，那么此时对岸的第0号人应该划船回来（耗时 t\[0\] ）
2.  船到达本岸后，应该让 第0号人 和 第 i 号人一起划船过河（耗时 t\[i\]）

> 即：dp\[i\] = dp\[i-1\] + t\[0\] + t\[i\]

*  如果前 i - 2 个人过河用时为dp\[i - 2\]

1.  现在在本岸又新增了第 i - 1 号，和第 i 号人，那么此时对岸的第0号人应该划船回来（耗时t\[0\]）
2.  船到达本岸后，应该让第 i - 1 号和第 i 号人一起划船过河（耗时t\[i\]）
3.  船到达对岸后，让对岸最快的第1号人划船回来（耗时t\[1\]）
4.  船到本岸后，第 0 号和第 1 号一起划船到对岸（耗时t\[1\]）

> 即 dp\[i\] = dp\[i-2\] + t\[0\] + t\[i\] + t\[1\] + t\[1\]

### Java算法源码 ###

import java.util.Arrays;
    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) {
        Arrays.sort(t);
        int[] dp = new int[n];
    
        if (n > 0) dp[0] = t[0];
        if (n > 1) dp[1] = t[1];
        if (n > 2) dp[2] = t[1] + t[0] + t[2];
    
        for (int i = 3; i < n; i++) {
          dp[i] = Math.min(dp[i - 1] + t[i] + t[0], dp[i - 2] + t[0] + t[i] + t[1] + t[1]);
        }
    
        return dp[n - 1];
      }
    }

### JavaScript算法源码 ###

### Python算法源码 ###

# 算法逻辑
    def getMinCrossRiverTime(n, t):
        t.sort()
    
        dp = [0]*n
    
        if n > 0:
            dp[0] = t[0]
        if n > 1:
            dp[1] = t[1]
        if n > 2:
            dp[2] = t[1] + t[0] + t[2]
        for i in range(3, n):
            dp[i] = min(dp[i-1] + t[i] + t[0], dp[i-2] + t[0] + t[i] + t[1] + t[1])
    
        return dp[n-1]
    
    
    # 输入获取
    T = int(input())
    
    for _ in range(T):
        n = int(input())
        t = list(map(int, input().split()))
        # 算法调用
        print(getMinCrossRiverTime(n, t))

[1700 -- Crossing River _poj.org]: http://poj.org/problem?id=1700
[TED_ - _ - _01_bilibili]: https://www.bilibili.com/video/BV1YW4y1z7jb/?spm_id_from=333.337.search-card.all.click&vd_source=b5105a99a0628dd906e154263279c518