[USACO07DEC] Bookshelf B

题意

给出若干奶牛身高和目标高度 B。选择尽量少的奶牛，使身高总和至少为 B。

思路

要让奶牛数量尽量少，每次都应该优先选择最高的奶牛。因此：

将身高从高到低排序；
从高到低累加；
第一次达到 B 时，当前数量就是答案。

这是直接的贪心排序题。

Python 知识

/home/rainboy/mycode/hugo-blog/content/program_language/python/sorting_and_ordering.md：sort(reverse=True) 可以降序排序。
/home/rainboy/mycode/hugo-blog/content/program_language/python/oj_input_output_cheatsheet.md：多行整数可用 sys.stdin.buffer.read() 统一读取。
break 在达到目标后提前结束循环。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19import sys


data = list(map(int, sys.stdin.buffer.read().split()))
n = data[0]
target = data[1]
heights = data[2:2 + n]
heights.sort(reverse=True)

total = 0
count = 0

for height in heights:
    total += height
    count += 1
    if total >= target:
        break

print(count)

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/**
 * 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-07-27 00:00
 * update_at: 2026-07-27 00:00
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 20005;

int n, target;
int h[MAXN]; // 奶牛身高

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

    cin >> n >> target;
    for (int i = 0; i < n; i++) {
        cin >> h[i];
    }

    // 从高到低排序
    sort(h, h + n, greater<int>());

    int sum = 0;
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        sum += h[i];
        cnt++;
        if (sum >= target) break;
    }

    cout << cnt << "\n";

    return 0;
}

复杂度

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

总结

“最少个数达到总和”且每个元素贡献独立时，优先选最大的元素是自然贪心。

[USACO07DEC] Bookshelf B

目录

题意

思路

Python 知识

代码

复杂度

总结