士兵过河问题

一、题目描述

一支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。

三、示例

四、解题思路

1. 核心思想

结合二分查找快速定位最大可行人数+经典多人过河问题的最优耗时公式，先通过二分法枚举可能的过河人数，再对每个人数计算其最短过河时间，最终找到 “耗时≤上限” 的最大人数及对应最短时间。核心是 “二分法缩小可行人数范围，经典公式保证耗时最优，两者结合高效求解”。

2. 问题本质分析

• 表层问题：在时间上限内找到最多过河的士兵数，并计算其最短耗时；
• 深层问题：

1. 人数与耗时的单调性：过河人数越多，最短耗时必然≥更少人数的最短耗时（单调性），因此可通过二分法高效枚举；
2. 过河耗时的最优解问题：经典多人过河问题的核心是 “让耗时短的士兵多往返划船”，通过固定公式可快速计算指定人数的最短耗时，无需暴力枚举路径；
3. 最优策略的选择：≥4 人时，两种策略的耗时对比是减少总耗时的关键，避免无效的往返；
4. 排序的必要性：优先选择耗时短的士兵过河，才能最大化可行人数（耗时短的人参与往返，总耗时更低）。

3. 核心逻辑

• 排序预处理：将士兵过河耗时升序排序，保证每次尝试的mid人都是耗时最短的（最大化可行人数）；
• 二分查找：利用 “人数越多，最短耗时越高” 的单调性，枚举可能的过河人数mid；
• 耗时计算：对每个mid，调用经典过河问题的最优耗时公式，计算mid人的最短过河时间；
• 边界调整：根据耗时与上限的关系，调整二分边界，记录满足条件的最大人数及对应耗时。

4. 步骤拆解

1. 输入预处理

   • 读取士兵数、时间上限、过河耗时数组，对耗时数组升序排序。

2. 二分查找初始化

   • 初始化二分边界：min=0（最少人数）、max=n（最多人数），初始化结果字符串ans。

3. 二分枚举过河人数

   • 循环条件：min ≤ max；
   • 计算中间值mid（当前尝试的过河人数）；
   • 截取前mid个耗时最短的士兵，调用getMinCrossRiverTime计算其最短耗时need；
   • 边界调整：
   • need > limit：mid人不可行，上界左移（max=mid-1）；
   • need < limit：mid人可行，记录结果，下界右移（min=mid+1）；
   • need = limit：记录结果并终止循环。

4. 最短耗时计算（getMinCrossRiverTime）

   • 剩余人数 = 1：耗时 = 唯一士兵的耗时；
   • 剩余人数 = 2：耗时 = 两人中较长的耗时；
   • 剩余人数 = 3：耗时 = 次短 + 最短 + 最长；
   • 剩余人数≥4：选两种策略的更优耗时，每轮处理 2 人，直到剩余人数 < 4。

5. 结果返回

   • 输出记录的 “最大人数 最短耗时”。

五、代码实现

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; } }