当前位置：首页 > article >正文

2021 年 12 月青少年软编等考 C 语言五级真题解析

article 2025/2/8 7:52:55

T1. 书架

John 最近买了一个书架用来存放奶牛养殖书籍，但书架很快被存满了，只剩最顶层有空余。

John 共有 $N$ 头奶牛 $(1 \leq N \leq 20, 000)$ ，每头奶牛有自己的高度 $H_i\ (1 ≤ H_i ≤ 10,000)$ ， $N$ 头奶牛的总高度为 $S$ 。书架高度为 $B\ (1 ≤ B ≤ S < 2,000,000,007)$ 。

为了到达书架顶层，奶牛可以踩着其他奶牛的背，像叠罗汉一样，直到他们的总高度不低于书架高度。当然若奶牛越多则危险性越大。为了帮助 John 到达书架顶层，找出使用奶牛数目最少的解决方案吧。

时间限制：1 s
内存限制：64 MB

输入
第 $1$ 行：空格隔开的整数 $N$ 和 $B$ 。
第 $2\sim N+1$ 行：第 $i + 1$ 行为整数 $H_i$ 。
输出
能达到书架高度所使用奶牛的最少数目。
样例输入
```
6 40
6
18
11
13
19
11
```
样例输出
```
3
```

思路分析

此题考查贪心算法中的最优装载问题，属于入门题。

最优装载问题的贪心策略是优先装最重的物品，此处即优先让高度最高的奶牛参与叠罗汉，然后依次是第二高、第三高 …，直到高度足以达到书架高度即可，此时的奶牛数量即为最少。

/*
 * Name: T1.cpp
 * Problem: 书架
 * Author: Teacher Gao.
 * Date&Time: 2025/02/05 13:55
 */

#include <cstdio>
#include <algorithm>

using namespace std;

int main()
{
   
    int high[20005] = {
   0};
    int n , b, tot = 0, ans = 0;
    scanf("%d %d", &n, &b);

    for (int i = 1; i <= n; ++i) {
   
        scanf("%d", &high[i]);
    }

    sort(high + 1, high + n + 1);

    for (int i = n; i >= 1; i--) {
   
        tot += high[i];
        ++ans;
        if (tot >= b) break;
    }

    printf("%d\n", ans);

    return 0;
}