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

发布于:2025-02-10 ⋅ 阅读:(125) ⋅ 点赞:(0)

T1. 书架

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

John 共有 N N N 头奶牛 ( 1 ≤ N ≤ 20 , 000 ) (1 ≤ N ≤ 20,000) (1N20,000),每头奶牛有自己的高度 H i   ( 1 ≤ H i ≤ 10 , 000 ) H_i\ (1 ≤ H_i ≤ 10,000) Hi (1Hi10,000) N N N 头奶牛的总高度为 S S S。书架高度为 B   ( 1 ≤ B ≤ S < 2 , 000 , 000 , 007 ) B\ (1 ≤ B ≤ S < 2,000,000,007) B (1BS<2,000,000,007)

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

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

  • 输入
    1 1 1 行:空格隔开的整数 N N N B B B
    2 ∼ N + 1 2\sim N+1 2N+1 行:第 i + 1 i+1 i+1 行为整数 H i H_i Hi
  • 输出
    能达到书架高度所使用奶牛的最少数目。
  • 样例输入
    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;
}

T2. 棋盘问题

在一个给定形状的棋盘(形状可能是不规则的)上面摆放棋子,棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列,请编程求解对于给定形状和大小的棋盘,摆放 k k k 个棋子的所有可行的摆放方案 C C C

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

  • 输入
    输入含有多组测试数据。每组数据的第一行是两个正整数 n , k n, k n,k,用一个空格隔开,表示了将在一个 n × n

网站公告

今日签到

点亮在社区的每一天
去签到