书架 - 题目列表

题目描述

有 $N$ 头奶牛，第 $i$ 头高 $H_i$ ，要把若干头奶牛叠起来使总高度不低于书架高度 $B$ ，求最少用几头（ $1\le N\le 20\,000$ ， $1\le H_i\le 10\,000$ ， $1\le B\le S<2\,000\,000\,007$ ， $S$ 为所有高度之和）。

输入第一行两个整数 $N,B$ ，接下来 $N$ 行每行一个 $H_i$ ；输出最少奶牛数。样例输入首行 6 40、随后六行依次为 6 18 11 13 19 11，输出 3。

思路

要让奶牛头数最少，就该让每头奶牛贡献的高度尽量大，所以把高度从大到小排序后依次累加，累加和首次 $\ge B$ 时用掉的奶牛数就是答案（ $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#!/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:42
# update_at: 2026-10-04 12:56

import sys
from itertools import accumulate


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, b = next(data), next(data)
    heights = sorted((next(data) for _ in range(n)), reverse=True)  # 从高到低叠放
    ans = next(
        (i + 1 for i, s in enumerate(accumulate(heights)) if s >= b),
        n,  # 一定能达到书架高度
    )
    print(ans)


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/**
 * 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 05:58
 * update_at: 2026-10-05 05:58
 */
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 20005;
int h[MAXN]; // h[i] 表示第 i 头奶牛的高度，值域只有 1..10000，用 int 即可

// 从高到低排序，让每头奶牛贡献的高度尽量大
bool cmp(int x, int y) {
    return x > y;
}

int main() {
    ll n, b;
    scanf("%lld %lld", &n, &b);
    for (ll i = 1; i <= n; i++) {
        scanf("%d", &h[i]);
    }
    sort(h + 1, h + n + 1, cmp);

    ll sum = 0; // 当前已叠奶牛的总高度
    ll ans = 0; // 已使用的奶牛头数
    for (ll i = 1; i <= n; i++) {
        sum += h[i];
        ans = i;
        // 总高度首次不低于书架高度，此时用掉的奶牛数最少
        if (sum >= b) {
            break;
        }
    }

    printf("%lld\n", ans);
    return 0;
}

书架

目录

题目描述

思路

参考代码