乘般过河

形式化题目

$n$ 人过河，船最多载 2 人，过河耗时 = 船上最慢者的时间。所有人过河的最少总耗时（划船返回的时间也按此计算）。

正解

思路

1. 贪心收尾

按时间升序排列，最快两人记 $a\le b$ ，最慢两人记 $c\le d$ 。每次处理最慢端，两种方案：

护送： $a,b$ 过河（ $b$ ）→ $a$ 划回（ $a$ ）→ $c,d$ 过河（ $d$ ）→ $b$ 划回（ $b$ ），合计 $a + 2b + d$ ，一次送走两人；
单送： $a,d$ 过河（ $d$ ）→ $a$ 划回（ $a$ ），合计 $a + d$ ，一次送走一人；走两次单送 $c,d$ 共 $2a + c + d$ 。

比较得： $2b < a + c$ 时护送更优，否则单送。剩 3 人及以下特判（ $a+b+c$ 或 $a$ 带走）。

2. 正确性直觉

最优解里最快的 $a$ 几乎总在划船，最慢者必须过河；两种收尾方案覆盖了「最慢两人一起走/分开走」的全部情形，局部最优可交换性保证贪心正确。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12/**
 * 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-10 11:30
 * update_at: 2026-10-10 11:30
 */

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){ios::sync_with_stdio(false);cin.tie(nullptr); int n; if(!(cin>>n)) return 0; vector<ll>a(n); for(int i=0;i<n;i++) cin>>a[i]; sort(a.begin(),a.end()); ll total=0; int l=0,r=n-1; while(r-l>2){ll aa=a[l],bb=a[l+1],cc=a[r-1],dd=a[r]; if(2*bb<aa+cc){total+=aa+2*bb+dd; r-=2;} else {total+=aa+dd; r--;}} total += (r-l==2 ? a[l]+a[l+1]+a[r] : a[r]); cout<<total<<'\n'; return 0;}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40#!/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-10-02 15:54
# update_at: 2026-10-02 15:54

import sys


def min_cross_time(people: list[int]) -> int:
    """升序数组从最慢的一端贪心送人：返回全部过河的最少总耗时。"""
    total = 0
    l, r = 0, len(people) - 1          # 还没过河的人是 people[l..r]
    while r - l > 2:                   # 人数 > 3 才需要在两种送法间选择
        a, b = people[l], people[l + 1]     # 最快的两人
        c, d = people[r - 1], people[r]     # 最慢的两人
        # 护送两人：a,b 过河(b)、a 划回(a)、c,d 过河(d)、b 划回(b)
        # 单送一人：a,d 过河(d)、a 划回(a)；分两次单送走 c,d 合计 2a+c+d
        # 护送比连续单送便宜（2b < a+c）时才一次送走最慢两人
        if 2 * b < a + c:
            total += a + 2 * b + d
            r -= 2
        else:
            total += a + d
            r -= 1
    # 剩 3 人：a 带最慢的过河后划回、再带次慢的过去（a+b+c）；剩 1、2 人直接上船
    total += sum(people[l:r + 1]) if r - l == 2 else people[r]
    return total


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    people = sorted(next(data) for _ in range(n))
    print(min_cross_time(people))


if __name__ == "__main__":
    solve()

复杂度

时间复杂度： $O(n\log n)$ （排序）。
空间复杂度： $O(n)$ 。

总结

「过河双人船」是贪心经典：两种收尾方案比大小即得最优。
记住比较式 $2b < a+c$ （护送优于连续单送的条件）。

目录

形式化题目

正解

思路

1. 贪心收尾

2. 正确性直觉

代码

复杂度

总结