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

蓝桥杯每日真题 - 第16天

article 2024/11/20 12:35:34

题目：（卡牌）

题目描述（13届 C&C++ B组C题）

解题思路：

题目分析：
- 有 n 种卡牌，每种卡牌的现有数量为 a[i]，所需的最大数量为 b[i]，还有 m 张空白卡牌。
- 每次组装一套卡牌，需要满足每种卡牌各一张的需求，若某种卡牌不足，可以用空白卡牌替代。
核心逻辑：
- 模拟构建套组的过程：
  - 优先使用 a[i] 中已有的卡牌；
  - 若 a[i] 不足，尝试使用空白卡牌 m 补充；
  - 若既没有足够的 a[i]，也没有空白卡牌 m 时，停止构建套组。
模拟过程：
- 使用一个循环依次检查每种卡牌的需求。
- 若当前可以满足所有需求，则增加已组装的套组数 r，否则结束循环。

代码实现（C语言）：

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
int a[200005];
int b[200005];
int main()
{
    int n,  i, r = 0, f = 1;
    long long int m;
    scanf("%d%d", &n, &m);
    for (i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }
    for (i = 0; i < n; i++)
    {
        scanf("%d", &b[i]);
    }
    while (f)
    {
        for (i = 0; i < n; i++)
        {
            if (a[i])
            {
                a[i]--;
            }
            else if (b[i] > 0 && m > 0)
            {
                b[i]--;
                m--;
            }
            else
            {
                f = 0;
                break;
            }
        }
        if (f)
        {
            r++;
        }
    }
    printf("%d", r);
}

得到运行结果：

代码分析：

输入处理：
- 读取 n（卡牌种类数）和 m（空白卡牌数）。
- 读取两组数组 a（现有卡牌数量）和 b（每类卡牌最大需求）。
模拟过程：
- 在每次循环中，逐一检查每种卡牌：
  - 若 a[i] > 0，使用一张已有卡牌；
  - 若 a[i] == 0 且 m > 0，用一张空白卡牌补充；
  - 若两者都无法满足，结束循环。
- 每成功完成一轮，增加套组数 r。
终止条件：
- 任意一种卡牌的需求无法满足，或空白卡牌数不足时，停止构建。
复杂度分析：
- 时间复杂度：O(k * n)，其中 k 是可以组装的最大套组数，n 是卡牌种类数。
- 空间复杂度：O(n)，用于存储数组 a 和 b。