吊桥1

题目描述

$n$ 只史莱姆要过一座吊桥，桥的最大载重为 $C$ ，每次最多同时过 2 只（也可 1 只独过），同一趟上的史莱姆重量和不得超过 $C$ ；每只过桥时间都是 $1$ ，求所有史莱姆过完的最短时间。

输入格式：第一行两个数 $n$ 和 $C$ ；第二行 $n$ 个数，表示每只史莱姆的重量。

输出格式：一个数，最短的过桥时间。

输入样例（ $n=5$ 、 $C=10$ ，重量 $1,2,3,4,5$ ）：

text

1
25 10
1 2 3 4 5

输出样例：3（由输入样例得到）。

数据范围： $1 \leq n \leq 10^5$ 。

思路

每趟耗时恒为 1，最短时间即最少趟数：把重量升序排序后用双指针，最重的一只必须走，若它加上当前最轻的不超过 $C$ 就同乘一趟，否则独占一趟。能配就配不劣于最优（趟数 $=n-$ 配对数），时间复杂度 $O(n \log n)$ 。

参考代码

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#!/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:41
# update_at: 2026-10-02 19:41

import sys


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)                    # 史莱姆数量
    cap = next(data)                  # 吊桥最大载重
    weight = sorted(next(data) for _ in range(n))    # 排序后最轻/最重才在两端

    # 最重的必须过桥：能和最轻的挤一趟就同乘，否则独占一趟。
    # 每趟耗时都是 1，趟数 = n - 成功同乘的对数，一趟最多消化两只。
    light, heavy = 0, n - 1
    trips = 0
    while light <= heavy:
        trips += 1
        if weight[light] + weight[heavy] <= cap:
            light += 1                 # 最轻的搭上这趟，向内收一格
        heavy -= 1                     # 最重的总是从这趟离开
    print(trips)


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/**
 * 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 <cstdio>
#include <algorithm>

typedef long long ll;

const int MAXN = 100005;

int n;              // 史莱姆数量
ll cap;             // 吊桥最大载重
ll a[MAXN];         // 每只史莱姆的重量

int main() {
    scanf("%d %lld", &n, &cap);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    std::sort(a + 1, a + n + 1);

    // 最重的必须过桥：能和最轻的挤一趟就同乘，否则独占一趟。
    // 每趟耗时都是 1，趟数 = n - 成功同乘的对数，一趟最多消化两只。
    int light = 1, heavy = n;
    ll trips = 0;
    while (light <= heavy) {
        trips++;
        if (a[light] + a[heavy] <= cap)
            light++;       // 最轻的搭上这趟，向内收一格
        heavy--;           // 最重的总是从这趟离开
    }
    printf("%lld\n", trips);
    return 0;
}

目录

题目描述

思路

参考代码