华为OD机试 - 士兵过河（Java & JS & Python）

深碍√TFBOYSˉ_ 2023-09-23 18:48 14阅读 0赞

### 题目描述 ###

一支N个士兵的军队正在趁夜色逃亡，途中遇到一条湍急的大河。  
敌军在T的时长后到达河面，没到过对岸的士兵都会被消灭。  
现在军队只找到了1只小船，这船最多能同时坐上2个士兵。

1.  当1个士兵划船过河，用时为 a\[i\]；0 <= i < N
2.  当2个士兵坐船同时划船过河时，用时为max(a\[j\],a\[i\])两士兵中用时最长的。
3.  当2个士兵坐船1个士兵划船时，用时为 a\[i\]\*10；a\[i\]为划船士兵用时。
4.  如果士兵下河游泳，则会被湍急水流直接带走，算作死亡。

请帮忙给出一种解决方案，保证存活的士兵最多，且过河用时最短。

### 输入描述 ###

第一行：N 表示士兵数(0<N<1,000,000)  
第二行：T 表示敌军到达时长(0 < T < 100,000,000)  
第三行：a\[0\] a\[1\] … a\[i\]… a\[N- 1\]  
a\[i\]表示每个士兵的过河时长。  
(10 < a\[i\]< 100; 0<= i< N）

### 输出描述 ###

第一行：”最多存活士兵数” “最短用时”

### 备注 ###

1）两个士兵的同时划船时，如果划速不同则会导致船原地转圈圈；所以为保持两个士兵划速相同，则需要向划的慢的士兵看齐。  
2）两个士兵坐船时，重量增加吃水加深，水的阻力增大；同样的力量划船速度会变慢；  
3）由于河水湍急大量的力用来抵消水流的阻力，所以2）中过河用时不是a\[i\] \*2，  
而是a\[i\] \* 10。

### 用例 ###

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td style="width:86px;">输入</td> 
   <td style="width:412px;">5<br> 43<br> 12 13 15 20 50</td> 
  </tr> 
  <tr> 
   <td style="width:86px;">输出</td> 
   <td style="width:412px;">3 40</td> 
  </tr> 
  <tr> 
   <td style="width:86px;">说明</td> 
   <td style="width:412px;">可以达到或小于43的一种方案：<br> 第一步：a[0] a[1] 过河用时：13<br> 第二步：a[0] 返回用时：12<br> 第三步：a[0] a[2] 过河用时：15</td> 
  </tr> 
 </tbody> 
</table>

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td style="width:86px;">输入</td> 
   <td style="width:412px;">5<br> 130<br> 50 12 13 15 20</td> 
  </tr> 
  <tr> 
   <td style="width:86px;">输出</td> 
   <td style="width:412px;">5 128</td> 
  </tr> 
  <tr> 
   <td style="width:86px;">说明</td> 
   <td style="width:412px;">可以达到或小于130的一种方案：<br> 第一步：a[1] a[2] 过河用时：13<br> 第二步：a[1] 返回用时：12<br> 第三步：a[0] a[4] 过河用时：50<br> 第四步：a[2] 返回用时：13<br> 第五步：a[1] a[2] 过河用时：13<br> 第六步：a[1] 返回用时：12<br> 第七步：a[1] a[3] 过河用时：15<br> 所以输出为：<br><code>5 128</code></td> 
  </tr> 
 </tbody> 
</table>

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td style="width:86px;">输入</td> 
   <td style="width:412px;">7<br> 171<br> 25 12 13 15 20 35 20</td> 
  </tr> 
  <tr> 
   <td style="width:86px;">输出</td> 
   <td style="width:412px;">7 171</td> 
  </tr> 
  <tr> 
   <td style="width:86px;">说明</td> 
   <td style="width:412px;"> <p>可以达到或小于171的一种方案：<br> 第一步：a[1] a[2] 过桥用时：13<br> 第二步：a[1] 带火把返回用时：12<br> 第三步：a[0] a[5] 过桥用时：35<br> 第四步：a[2] 带火把返回用时：13<br> 第五步：a[1] a[2] 过桥用时：13<br> 第六步：a[1] 带火把返回用时：12<br> 第七步：a[4] a[6] 过桥用时：20<br> 第八步：a[2] 带火把返回用时：13<br> 第九步：a[1] a[3] 过桥用时：15<br> 第十步：a[1] 带火把返回用时：12<br> 第十一步：a[1] a[2] 过桥用时：13</p> <p>所以输出为：</p> <p><code>7 171</code></p> </td> 
  </tr> 
 </tbody> 
</table>

### 题目解析 ###

本题是 [POJ - 1700 Crossing River\_伏城之外的博客-CSDN博客][POJ - 1700 Crossing River_-CSDN] 的变种题。

建议大家先搞定这题，然后再来看本题。

本题在前面这题的基础上，多了一个过河时间限制，以及要求最多存活士兵（即在限制时间内过最多的人）

对于贪心解法，可以结合二分法来求解本题。

即在0~N中尝试找到成功过河的人数，其中0指的是成功过河的人数为0个，N指的是成功过河的人数为N个。

将二分法找到的可能人数mid带入上面POJ-1700的逻辑中，计算出mid个人都过河所需的最短时间need，将need和本题过河时间限制limit进行比较：

*  若 need > limit，则说明当前mid个人无法成功过河，即过河人数偏多了，我们应该减少过河人数
 *  若 need < limit，则说明当前mid个人可以成功过河，但是可能还可以过更多人数
 *  若 need == limit，则说明当前mid个人刚刚好可以在limit时间过完河，则此时mid就是最多存货的士兵数

对于动态规划解法，由于是从0人过河递推到N人过河，因此不需要二分尝试过河人数，而是可以直接基于dp\[i\]来实时比较T，如果超过了T，则说明只能过河 i 人，耗时dp\[i-1\]

另外，本题中说：

> 当2个士兵坐船1个士兵划船时，用时为 a\[i\]\*10；a\[i\]为划船士兵用时。

假设x士兵划船用时为a\[x\]，y士兵划船用时为a\[y\]，a\[x\] < a\[y\]

这句话的意思是：如果x,y一起划船，有两种过河时间，分别是：

*  a\[x\] \* 10
 *  a\[y\]

如果a\[y\] > a\[x\] \* 10，我们应该选择a\[x\] \* 10，即让较快的士兵单独划船过河，这样耗时更短。

但是，本题中又说：

> (10 < a\[i\]< 100; 0<= i< N）

即

*  10 < a\[y\] < 100
 *  10 < a\[x\] < 100

那么必然：100 < a\[x\] \* 10 < 1000

即必然 a\[x\] \* 10 > a\[y\]

因此，我们不需要考虑上面那种两个士兵坐船，一个士兵划船的情况。

## 贪心解法 ##

### JavaScript算法源码 ###

/* JavaScript Node ACM模式 控制台输入获取 */
    const readline = require("readline");
    
    const rl = readline.createInterface({
      input: process.stdin,
      output: process.stdout,
    });
    
    const lines = [];
    rl.on("line", (line) => {
      lines.push(line);
    
      if (lines.length === 3) {
        const N = lines[0] - 0;
        const T = lines[1] - 0;
        const times = lines[2].split(" ").map(Number);
        console.log(getResult(N, T, times));
        lines.length = 0;
      }
    });
    
    /**
     *
     * @param {*} n 士兵数
     * @param {*} limit 过河时间上限
     * @param {*} times 数组，元素表示每个士兵的过河时长
     * @return {*} ”最多存活士兵数” “最短用时”
     */
    function getResult(n, limit, times) {
      // 过河时间升序
      times.sort((a, b) => a - b);
    
      // 最少成功过河人数
      let min = 0;
      // 最多成功过河人数
      let max = n;
    
      // 记录题解
      let ans = "";
    
      // 二分法取可能成功的过河人数
      while (min <= max) {
        // mid是过河人数
        const mid = Math.floor((min + max) / 2);
        // 计算mid个人过河所需的最短时间need
        const need = getMinCrossRiverTime(mid, times.slice(0, mid));
    
        // 如果need超过了过河时间上限limit，那么说明能成功过河的人没这么多
        if (need > limit) {
          max = mid - 1;
        } else if (need < limit) {
          // 如果need小于过河时间上限limit，那么说明mid个最快的人可以在limit时间内成功过河
          ans = `${mid} ${need}`;
          // 但是可能还可以过更多人
          min = mid + 1;
        } else {
          // 如果need == limit，那么说明过河人数刚好可以在limit时间内成功过河，此时可以直接返回
          ans = `${mid} ${need}`;
          break;
        }
      }
    
      return ans;
    }
    
    // 计算n个人运到河对岸所需要花费的最少时间
    function getMinCrossRiverTime(n, t) {
      let cost = 0;
    
      while (n > 0) {
        if (n == 1) {
          cost += t[0];
          break;
        } else if (n == 2) {
          cost += t[1];
          break;
        } else if (n == 3) {
          cost += t[1] + t[0] + t[2];
          break;
        } else {
          cost += Math.min(
            t[n - 1] + t[0] + t[n - 2] + t[0],
            t[1] + t[0] + t[n - 1] + t[1]
          );
          n -= 2;
        }
      }
    
      return cost;
    }

### Java算法源码 ###

import java.util.Arrays;
    import java.util.Scanner;
    
    public class Main {
      public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
    
        int n = sc.nextInt();
        int t = sc.nextInt();
    
        int[] times = new int[n];
    
        for (int i = 0; i < n; i++) {
          times[i] = sc.nextInt();
        }
    
        System.out.println(getResult(n, t, times));
      }
    
      /**
       * @param n 士兵数
       * @param limit 过河时间上限
       * @param times 数组，元素表示每个士兵的过河时长
       * @return ”最多存活士兵数” “最短用时”
       */
      public static String getResult(int n, int limit, int[] times) {
        // 过河时间升序
        Arrays.sort(times);
    
        // 最少成功过河人数
        int min = 0;
        // 最多成功过河人数
        int max = n;
    
        // 记录题解
        String ans = "";
    
        // 二分法取可能成功的过河人数
        while (min <= max) {
          // mid是过河人数
          int mid = (min + max) / 2;
          // 计算mid个人过河所需的最短时间need
          int need = getMinCrossRiverTime(mid, Arrays.copyOfRange(times, 0, mid));
    
          // 如果need超过了过河时间上限limit，那么说明能成功过河的人没这么多
          if (need > limit) {
            max = mid - 1;
          } else if (need < limit) {
            // 如果need小于过河时间上限limit，那么说明mid个最快的人可以在limit时间内成功过河
            ans = mid + " " + need;
            // 但是可能还可以过更多人
            min = mid + 1;
          } else {
            // 如果need == limit，那么说明过河人数刚好可以在limit时间内成功过河，此时可以直接返回
            ans = mid + " " + need;
            break;
          }
        }
    
        return ans;
      }
    
      // 计算将n个人运到河对岸所需要花费的最少时间
      public static int getMinCrossRiverTime(int n, int[] t) {
        int cost = 0;
    
        while (n > 0) {
          if (n == 1) {
            cost += t[0];
            break;
          } else if (n == 2) {
            cost += t[1];
            break;
          } else if (n == 3) {
            cost += t[1] + t[0] + t[2];
            break;
          } else {
            cost += Math.min(t[n - 1] + t[0] + t[n - 2] + t[0], t[1] + t[0] + t[n - 1] + t[1]);
            n -= 2;
          }
        }
    
        return cost;
      }
    }

### Python算法源码 ###

# 输入获取
    n = int(input())
    t = int(input())
    times = list(map(int, input().split()))
    
    
    # 计算n个人运到河对岸所需要花费的最少时间
    def getMinCrossRiverTime(n, t):
        cost = 0
    
        while n > 0:
            if n == 1:
                cost += t[0]
                break
            elif n == 2:
                cost += t[1]
                break
            elif n == 3:
                cost += t[1] + t[0] + t[2]
                break
            else:
                cost += min(t[n - 1] + t[0] + t[n - 2] + t[0], t[1] + t[0] + t[n - 1] + t[1])
                n -= 2
    
        return cost
    
    
    # 算法入口
    def getResult(n, limit, times):
        """
        :param n: 士兵数
        :param limit: 过河时间上限
        :param times: 数组，元素表示每个士兵的过河时长
        :return: ”最多存活士兵数” “最短用时”
        """
        times.sort()
    
        # 最少成功过河人数
        low = 0
        # 最多成功过河人数
        high = n
    
        # 记录题解
        ans = ""
    
        # 二分法取可能成功的过河人数
        while low <= high:
            # mid是过河人数
            mid = (low + high) // 2
            # 计算mid个人过河所需的最短时间need
            need = getMinCrossRiverTime(mid, times[:mid])
    
            # 如果need超过了过河时间上限limit，那么说明能成功过河的人没这么多
            if need > limit:
                high = mid - 1
            elif need < limit:
                # 如果need小于过河时间上限limit，那么说明mid个最快的人可以在limit时间内成功过河
                ans = f"{mid} {need}"
                # 但是可能还可以过更多人
                low = mid + 1
            else:
                # 如果need == limit，那么说明过河人数刚好可以在limit时间内成功过河，此时可以直接返回
                ans = f"{mid} {need}"
                break
    
        return ans
    
    
    # 算法调用
    print(getResult(n, t, times))

## 动态规划解法（100%通过率） ##

### Java算法源码 ###

### JavaScript算法源码 ###

### Python算法源码 ###

# 输入获取
    n = int(input())
    T = int(input())
    times = list(map(int, input().split()))
    
    
    # 算法入口
    def getResult(n, limit, t):
        """
        :param n: 士兵数
        :param limit: 过河时间上限
        :param t: 数组，元素表示每个士兵的过河时长
        :return: ”最多存活士兵数” “最短用时”
        """
        times.sort()
    
        dp = [0] * n
    
        for i in range(n):
            if i == 0:
                dp[0] = t[0]
                if dp[0] > limit:
                    return "0 0"
            elif i == 1:
                dp[1] = t[1]
            else:
                dp[i] = min(dp[i - 1] + t[i] + t[0], dp[i - 2] + t[0] + t[i] + t[1] + t[1])
    
            if dp[i] > limit:
                return str(i) + " " + str(dp[i - 1])
    
        return str(n) + " " + str(dp[n - 1])
    
    
    # 算法调用
    print(getResult(n, T, times))

[POJ - 1700 Crossing River_-CSDN]: https://blog.csdn.net/qfc_128220/article/details/130143621