修理牛棚

题目描述

编号 $1 \sim S$ 的牛棚排成一行，其中 $C$ 个有牛。可买至多 $M$ 块木板，每块覆盖一个连续区间，要求所有有牛牛棚都被覆盖，求木板总长度最小值。

数据范围： $1 \le M \le 50$ ， $1 \le S \le 200$ ， $1 \le C \le S$ 。

思路

先假设用一整块板覆盖最左到最右的有牛牛棚。相邻有牛牛棚之间的空棚间隙如果越大，在这里断开越省长度。因此把间隙从大到小排序，切掉前 $k-1$ 大的间隙（ $k = \min(M, C)$ ），答案等于整块长度减去这些间隙之和。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11import sys

def main() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    m, s, c = next(data), next(data), next(data)
    a = sorted(next(data) for _ in range(c))
    # 从“一整块板 [a[0], a[-1]]”开始，允许再切 m-1 刀
    gaps = [y - x - 1 for x, y in zip(a, a[1:])]
    print(a[-1] - a[0] + 1 - sum(sorted(gaps, reverse=True)[:m - 1]))

main()

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/**
 * 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 09:25
 * update_at: 2026-10-06 09:25
 */
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXC = 205;

ll a[MAXC]; // 有牛牛棚编号
ll gaps[MAXC]; // 相邻间隙

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

    ll m, s, c;
    cin >> m >> s >> c;
    for (int i = 1; i <= c; ++i) cin >> a[i];
    sort(a + 1, a + c + 1);

    // 整块板覆盖 [a[1], a[c]]，然后切最大的 k-1 个间隙
    int k = (int)min(m, c); // 实际使用的板数
    for (int i = 1; i < c; ++i) gaps[i] = a[i + 1] - a[i] - 1;
    sort(gaps + 1, gaps + c); // 升序
    reverse(gaps + 1, gaps + c); // 转成降序

    ll total = a[c] - a[1] + 1;
    for (int i = 1; i <= k - 1 && i < c; ++i) total -= gaps[i];
    cout << total << "\n";
    return 0;
}

目录

题目描述

思路

参考代码