排序后按最慢者递推：最快者往返快递一人，或两名最快者摆渡两名最慢者，逐个取较小值。
OJ: roj
题目 ID: 1232
难度:普及-
标签:贪心动态规划排序python
创建: 2026-09-30 00:56
更新: 2026-10-05 06:04
题目描述
t 组数据，每组 n 个人要过河：船每次最多载 2 人，且至少 1 人把船划回，用时由船上较慢者决定，求把所有人送到对岸的最少总时间。输入第一行 t，之后每组第一行为 n、第二行为 n 个过河时间；输出每组一行答案。数据范围 1 / 4 / 1 2 5 10，输出 17。
思路
先排序，让当前最慢者永远是末尾；每轮只送走最慢者，要么最快者往返快递他一人（代价
参考代码
Python 版：
python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 00:56
# update_at: 2026-09-30 00:56
import sys
from collections.abc import Iterator
def cross(times: list[int]) -> int:
"""返回 times 中所有人过河的最短总时间（已升序）。
dp[i] = 送走最慢的 i+1 个人所需时间。送走最慢者 a[i] 只有两种不交叉的运输剧本，
每轮都让 a[0] 或 a[1] 划船回来，故 dp[i] = min(dp[i-1] + a[0] + a[i],
dp[i-2] + a[0] + 2*a[1] + a[i])。原地滚动两个变量即可，不必开数组。
"""
dp_prev2: int = times[0] # dp[0]：只剩一人时他自己过河
if len(times) == 1:
return dp_prev2
dp_prev1: int = times[1] # dp[1]：两人一起过河，慢者定速
for i in range(2, len(times)):
# best 方案：最快者来回送最慢者，一次只消耗掉一个最慢者
solo = dp_prev1 + times[0] + times[i]
# duo 方案：最快两人先过、次快者带船回、两慢者同过、最快者带船回
duo = dp_prev2 + times[0] + 2 * times[1] + times[i]
dp_prev2, dp_prev1 = dp_prev1, min(solo, duo) # 滚动：省掉长度 n 的数组
return dp_prev1
def solve() -> None:
"""逐组读入 n 与 n 个过河时间，输出每组的最短总时间。"""
data: Iterator[int] = iter(map(int, sys.stdin.buffer.read().split()))
out: list[str] = []
for _ in range(next(data)): # 组数 t，每组输出一行
n = next(data)
times = sorted(next(data) for _ in range(n)) # 只有有序才能按"最慢者"递推
out.append(str(cross(times)))
print('\n'.join(out))
if __name__ == "__main__":
solve()C++ 版（同一算法）：
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-05 06:04
* update_at: 2026-10-05 06:04
*/
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 1005;
ll a[MAXN]; // a[i] 表示第 i 个人单独划船过河所需的时间，已按升序排列
// 求把 a[0..n-1] 全部送到对岸的最少总时间。
// 每次只送走当前最慢的人，有两种剧本：最快者往返快递一人，或两名最快者摆渡两名最慢者。
ll crossing_river(int n) {
if (n == 1) {
return a[0]; // 只剩一人，他自己划过去
}
ll dp_prev2 = a[0]; // dp[0]：只有一个人的花费
ll dp_prev1 = a[1]; // dp[1]：两人一起过去，耗时由慢者决定
for (int i = 2; i < n; i++) {
// 方案 A：最快者送最慢者过去，自己再划回来，本轮只送走一人
ll solo = dp_prev1 + a[0] + a[i];
// 方案 B：两名最快者先把船送到对岸，两名最慢者同船过去，本轮送走两人
ll duo = dp_prev2 + a[0] + 2 * a[1] + a[i];
ll best = min(solo, duo);
dp_prev2 = dp_prev1;
dp_prev1 = best;
}
return dp_prev1; // 即 dp[n-1]
}
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
// 先排序：只有有序，"当前最慢的人"才是末尾那个人
sort(a, a + n);
cout << crossing_river(n) << "\n";
}
return 0;
}