一、题目背景

本题为2021年省赛填空题

• C/C++A组第1题
• C/C++B组第2题
• Java B组第2题
• Java B组第3题
• Python组第1题

二、题目描述

小蓝有很多数字卡片，每张卡片上都是数字 0 到 9。
小蓝准备用这些卡片来拼一些数，他想从 1 开始拼出正整数，每拼一个就保存起来，卡片就不能用来拼其它数了。小蓝想知道自己能从 1 拼到多少。例如，当小蓝有 30 张卡片，其中 0到9各3 张，则小蓝可以拼出 1到 10。但是拼 11 时卡片 1 已经只有一张了，不够拼出 11。

现在小蓝手里有 0到9 的卡片各 2021 张，共 20210 张，请问小蓝可以从 1拼到多少?
提示:建议使用计算机编程解决问题。

三、题目分析

本题是一道非常典型的基础枚举题。想求出最多拼到多少，那就从1开始一直往后枚举，枚举的过程中检查这个数是不是符合条件，如果符合卡片条件就继续枚举，直到不符合条件为止（卡片不够了）。
所以这道题的核心就转到了 如何检查 上。

1.检查思路

我们可以申请一个下标分别从0到9的数组，对应卡片从0~9，让每一个数组的值都为卡牌的总数量大小：2021。
然后通过取余的方式，将每一位对应的数字求出来，然后看看这些对应位置的数的数量是不是符合卡牌的数量。

取余求每个位置的数 ：
例如： 求 189的每一位数的大小
个位： 189%10 = 9
十位： （189/10）%10 = 8
百位： （189/10/10）%10 = 1

下面我用C语言写一下这段起检查作用的函数

#include<stdio.h>
int card[10];                 // （1）
int check(int num)            // （2）
{
    while (num)
    {
        int a = num % 10;    //（3）
        if (card[a] > 0)    //（4）
            card[a]--;        //（5）
        else                
            return 0;        //（6）
        num = num / 10;        //（7）
    }
    return 1;                
}

• （1）申请下标分别从0到9的数组，用来存卡片
• （2）num表示需要检查的数
• （3）求每一位的数是多少
• （4）判断这个数对应的卡牌还有没有
• （5）如果有，就符合要求，但是用过了这张卡牌所以减一
• （6）如果没有，就不符合要求
• （7）改变位数（将百位变为十位，十位变为个位......）

2.思路优化

上面的思路，其实已经能够完成检查的任务，但是如果仔细想想，其实枚举是从1开始，那么消耗卡片1的数量是最多的。卡片1的数量是最先小于0，所以我们只需要检查卡片1的数量就可以了。

下面我用C语言写一下优化后的函数

#include<stdio.h>
int card[10];  
int check(int num)
{
    while (num)
    {
        int a = num % 10;        //（1）
        if (a == 1)                //（2）
            if (card[1] == 0)    //（3）
                return 0;
            else
                card[1]--;        //（4）
        num = num / 10;            //（5）
    }
    return 1;
}

• （1）求每一位的数是多少
• （2）如果这一位是1
• （3）如果卡牌1的数量等于0，结束检查
• （4）如果不为0，卡牌1的数量减一
• （5）改变位数（将百位变为十位，十位变为个位......）

四、代码汇总

1.C语言代码

C语言里面没有bool类型，但是C语言中0代表假，非0代表真。

#include<stdio.h>
int card[10];  
int check(int num)
{
    while (num)
    {
        int a = num % 10;
        if (a == 1)
            if (card[1] == 0)
                return 0;
            else
                card[1]--;
        num = num / 10;
    }
    return 1;
}
int main()
{
    for (int i = 0; i <= 9; i++)
        card[i] = 2021;               //(1)
    for (int i = 1;check(i); i++)     //(2)
    {
        printf("%d\n", i );         //(3)
    }
    return 0;
}

（1）循环，让每个卡牌的数量都为2021个
（2）逐个枚举检查
（3）输出符合的正确的结果

2. C++代码

C++代码和C语言代码大致差不多，不同的是C++里面有bool类型。

当然printf也可也用c++里面的cout代替

cout不需要记太多的占位符，更加方便。

#include<iostream>
using namespace std;
int card[10];  
bool check(int num)
{
    while (num)
    {
        int a = num % 10;
        if (a == 1)
            if (card[1] == 0)
                return false;
            else
                card[1]--;
        num = num / 10;
    }
    return true;
}
int main()
{
    for (int i = 0; i <= 9; i++)
    {
        card[i] = 2021;
    }
    for (int i = 1;check(i); i++)
    {
        cout << i << endl;
    }
    return 0;
}

3.运行结果

故最终答案为：3181

五、总结

1.枚举思想

枚举就是是从问题所有可能的解的集合中一一枚举出各种元素。

并且用题目中给定的检验条件判定哪些元素是错误的，哪些是正确的。

2.取余求位数

取余求各个位数是常用的基本功。
不管是几位数个位数都可以直接使用 数 % 10 来取余数获得
至于获取十位数，百位数，只需要处于10或100再进行取余即可获得。