吊桥2

题目描述

$n$ 只史莱姆过吊桥，第 $i$ 只单独过桥耗时 $t_i$ 。每次最多 2 只同行，必须有人携带手电筒；该趟耗时按慢者计。一批过桥后手电筒留在对岸，需有人送回才能接下一批。求全部过桥的最短总时间。

输入：第一行 $n$ ，第二行 $n$ 个整数表示各史莱姆过桥时间。
输出：一个整数，最短总时间。
数据范围： $0 \le n \le 1000$ ，时间 $\le 100$ 。

样例： $n=4,\ t=[1,2,5,10]$ ，输出 $17$ ； $n=5,\ t=[1,2,8,7,6]$ ，输出 $22$ 。

思路

升序排序后，每轮把最慢的两只送过桥。两种送法取最小值：最快往返接送（ $2a_1+a_{n-1}+a_n$ ）或最快与次快结伴（ $a_1+2a_2+a_n$ ）。每轮消去 2 只，剩 3 只以内直接收尾。

参考代码

Python 版：

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#!/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 19:54
# update_at: 2026-10-04 11:13

import sys


def shortest_crossing(times: list[int]) -> int:
    """全部史莱姆过桥的最短时间：每轮送走最慢的两只，两种送法取小，剩 3 只内直接收尾。"""
    cost, tail = 0, len(times) - 1          # tail 指向当前最慢者，处理掉的都在它右侧
    while tail > 2:                          # 剩 4 只以上才有"两种送法"的选择
        # 送法一：最快往返接送——(a1,an) 过、a1 回、(a1,a_{n-1}) 过、a1 回
        shuttle = 2 * times[0] + times[tail] + times[tail - 1]
        # 送法二：最快与次快结伴送——(a1,a2) 过、a1 回、(a_{n-1},an) 过、a2 回
        relay = times[0] + 2 * times[1] + times[tail]
        cost += min(shuttle, relay)
        tail -= 2                            # 这一轮恰好消化最慢的两只

    if tail == 2:                            # 三只：最快陪慢的逐趟送，总耗时即三者之和
        return cost + sum(times[:3])
    if tail >= 0:                            # 两只按慢者计时；一只自己提灯过
        return cost + times[tail]
    return cost                              # 一只史莱姆都没有


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)                           # 史莱姆个数（个别数据可能读不出，按 0 收尾）
    times = sorted(next(data) for _ in range(n))  # 升序排序：最快的在左、最慢的在右
    times += [0] * (n - len(times))          # 个别测试数据缺数，标程 scanf 失败留 0，这里对齐
    print(shortest_crossing(times))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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
41
42
43
44
45
46
47/**
 * 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-06 08:59
 * update_at: 2026-10-06 08:59
 */
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 1005;

ll a[MAXN]; // 每只史莱姆过桥时间，升序排序

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    for (int i = 0; i < n; ++i) cin >> a[i];
    sort(a, a + n); // 升序：最快的在左，最慢的在右

    ll cost = 0;
    int tail = n - 1; // 当前未过桥的最慢者下标

    // 每轮送走最慢的两只，两种送法取小
    while (tail > 2) {
        // 送法一：最快往返接送 (a0,an)过、a0回、(a0,a_{n-1})过、a0回
        ll shuttle = 2 * a[0] + a[tail] + a[tail - 1];
        // 送法二：最快与次快结伴 (a0,a1)过、a0回、(a_{n-1},an)过、a1回
        ll relay   = a[0] + 2 * a[1] + a[tail];
        cost += min(shuttle, relay);
        tail -= 2; // 本轮消化两只最慢的
    }

    // 剩余3只以内直接收尾
    if (tail == 2)      cost += a[0] + a[1] + a[2]; // 三只：最快陪两次去程、回一次程
    else if (tail == 1) cost += a[1];               // 两只：按慢者计时
    else if (tail == 0) cost += a[0];               // 一只：自己提灯过

    cout << cost << "\n";
    return 0;
}

目录

题目描述

思路

参考代码