有n个人一条船，所有人要从左岸渡船到右岸，第i个人过河时间是 𝑎 𝑖 。船上最多坐两个人，船从右岸回到左岸时必须保证船上有人。 每次船的行驶时间等于船上两人中过河时间的较大值。 问过河所需最短时间。 输入 第1行输入n; 第2行输入n个数，表示每个人过河的时间。 输出 输出过河最少时间。 样例输入 复制 4 1 2 5 10 样例输出 复制 17 提示

问题分析 n个人从左岸到右岸，船最多载两人，返回时船上必须有人。 每次船行时间 = 船上两人中较慢的过河时间。 目标：求所有人过河的最短时间。 核心思路 将过河时间从小到大排序： \[ a_1 \leq a_2 \leq \dots \leq a_n \] 考虑两种策略运送最慢的两人（\(a_{n-1}\) 和 \(a_n\)）： 1. 最快两人来回送 - 步骤： \(a_1, a_2\) 过去（时间 \(a_2\)） \(a_1\) 回来（时间 \(a_1\)） \(a_{n-1}, a_n\) 过去（时间 \(a_n\)） \(a_2\) 回来（时间 \(a_2\)） - 总时间： \[ T_1 = a_2 + a_1 + a_n + a_2 = a_1 + 2a_2 + a_n \] 2. 最快的人分别送 - 步骤： \(a_1, a_n\) 过去（时间 \(a_n\)） \(a_1\) 回来（时间 \(a_1\)） \(a_1, a_{n-1}\) 过去（时间 \(a_{n-1}\)） \(a_1\) 回来（时间 \(a_1\)） - 总时间： \[ T_2 = a_n + a_1 + a_{n-1} + a_1 = 2a_1 + a_{n-1} + a_n \] 每次选择两种策略中较优的，直到剩余人数 ≤ 3。 边界情况 - n = 1：直接过去，时间 \(a_1\) - n = 2：两人一起过去，时间 \(a_2\) - n = 3：最快的人分两次送，时间 \(a_1 + a_2 + a_3\) 算法步骤 1. 排序 \(a\) 2. 初始化总时间 \(time = 0\) 3. 当 \(n > 3\) 时： - 计算 \(T_1 = a_1 + 2a_2 + a_n\) - 计算 \(T_2 = 2a_1 + a_{n-1} + a_n\) - \(time += \min(T_1, T_2)\) - \(n -= 2\)（移除最慢的两人） 4. 处理剩余人数： - n = 1：\(time += a_1\) - n = 2：\(time += a_2\) - n = 3：\(time += a_1 + a_2 + a_3\) 5. 输出 \(time\) 样例验证 输入： ``` 4 1 2 5 10 ``` 排序后：\(a = [1, 2, 5, 10]\) n = 4 > 3： \(T_1 = 1 + 2 \times 2 + 10 = 15\) \(T_2 = 2 \times 1 + 5 + 10 = 17\) 选 \(T_1 = 15\)，time = 15，n = 2 剩余 n = 2：time += 2，总时间 = 17 ✅ 代码实现 ```python n = int(input()) a = list(map(int, input().split())) a.sort() time = 0 while n > 3: t1 = a[0] + 2 * a[1] + a[n - 1] t2 = 2 * a[0] + a[n - 2] + a[n - 1] time += min(t1, t2) n -= 2 if n == 3: time += a[0] + a[1] + a[2] elif n == 2: time += a[1] elif n == 1: time += a[0] print(time) ``` [2026-01-11 17:31:41 | AI问答 | 949点数解答]