刷题笔记合集🔗

问题描述

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

1. 当 1 个士兵划船过河，用时为 ；
2. 当 2 个士兵坐船同时划船过河时，用时为 两士兵中用时最长的。
3. 当 2 个士兵坐船 1 个士兵划船时，用时为 ； 为划船士兵用时。
4. 如果士兵下河游泳，则会被湍急水流直接带走，算作死亡。

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

输入格式

第一行： 表示士兵数
第二行： 表示敌军到达时长
第三行： … …
表示每个士兵的过河时长。

输出格式

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

样例输入1

5
43
12 13 15 20 50

样例输出1

3 40

样例输入2

5
130
50 12 13 15 20

样例输出2

5 128

样例输入3

7
171
25 12 13 15 20 35 20

样例输出3

7 171

样例解释

数据范围

题解

这道题是经典的"过河问题"的变种，主要难点在于既要保证存活士兵最多，又要保证过河用时最短。

首先，我们需要理解题目的核心：

1. 船最多坐2人
2. 过河方式有两种：一人划船或两人同时划船
3. 有时间限制T，超过T的士兵会被消灭

解决这个问题的关键是找到最优的过河策略。我们可以采用两种思路：

思路一：动态规划

我们可以定义dp[i]表示让前i个士兵过河所需的最短时间。通过递推关系，我们可以得到：

• 当i=1时，dp[1] = a[0]
• 当i=2时，dp[2] = a[1]
• 当i>2时，dp[i] = min(dp[i-1] + a[0] + a[i-1], dp[i-2] + a[0] + a[i-1] + a[1] + a[1])

这里的递推公式基于一个重要观察：让最快的人（a[0]）负责来回运送其他人是最优的。

在计算过程中，一旦发现dp[i] > T，说明只能让i-1个人过河，此时返回结果为"i-1 dp[i-1]"。

思路二：二分查找 + 贪心

另一种思路是通过二分查找确定能够过河的最大人数，然后用贪心算法计算最短时间。

1. 对士兵按过河时间排序
2. 二分查找可能的过河人数mid
3. 计算mid个人过河所需的最短时间need
4. 比较need和T，调整二分查找的范围

时间复杂度分析：

• 排序需要O(N log N)
• 二分查找需要O(log N)
• 每次计算过河时间需要O(N)
• 总体时间复杂度为O(N log N)

对于给定的数据范围（N可达1,000,000），这个算法是高效的。

参考代码

# 输入获取
n = int(input())
t_lim = int(input())
cross_t = list(map(int, input().split()))

# 算法实现
def solve_prob(n_sol, t_max, t_arr):
    """
    计算最多存活士兵数和最短用时
    
    参数:
    n_sol: 士兵总数
    t_max: 敌军到达时间上限
    t_arr: 每个士兵的过河时长数组
    
    返回:
    最多存活士兵数和最短用时的字符串
    """
    # 按过河时间排序
    t_arr.sort()
    
    # 初始化dp数组
    dp_time = [0] * n_sol
    
    # 动态规划计算
    for i in range(n_sol):
        if i == 0:
            # 第一个士兵直接过河
            dp_time[0] = t_arr[0]
            # 如果第一个士兵都无法在限制时间内过河，则无人能存活
            if dp_time[0] > t_max:
                return "0 0"
        elif i == 1:
            # 两个士兵同时过河，取较慢的时间
            dp_time[1] = t_arr[1]
        else:
            # 计算让i+1个士兵过河的最短时间
            # 方案1: 先让i个士兵过河，然后最快的士兵回来，再和第i+1个士兵一起过河
            plan_a = dp_time[i-1] + t_arr[0] + t_arr[i]
            # 方案2: 先让i-1个士兵过河，然后第二快的士兵回来，最快和最慢的一起过河，
            # 然后最快的回来，再和第二快的一起过河
            plan_b = dp_time[i-2] + t_arr[0] + t_arr[i] + t_arr[1] + t_arr[1]
            # 取两种方案中较快的
            dp_time[i] = min(plan_a, plan_b)
        
        # 检查是否超过时间限制