第 13 届 "蓝桥杯 "C++B 全国竞赛 C 题 - 纸牌 (AC)

参赛话题：​​算法题解​​

目录

• ​​1.卡牌​​

• ​​1.问题描述​​
• ​​2.输入格式​​
• ​​3.输出格式​​
• ​​4.样例输入​​
• ​​5.样例输出​​
• ​​6.数据范围​​
• ​​7.原题链接​​

• ​​2.解题思路​​
• ​​3.Ac_code​​

1.卡牌

1.问题描述

这天, 小明在整理他的卡牌。

他一共有 n 种卡牌, 第 i种卡牌上印有正整数数 且第 i 种卡牌 现有 张。
而如果有 n 张卡牌, 其中每种卡牌各一张, 那么这 n 张卡牌可以被称为一 套牌。小明为了凑出尽可能多套牌, 拿出了 m 张空白牌, 他可以在上面写上数 i, 将其当做第 i 种牌来凑出套牌。然而小明觉得手写的牌不太美观, 决定第 i 种牌最多手写 张。

请问小明最多能凑出多少套牌?

2.输入格式

输入共 3 行, 第一行为两个正整数

第二行为 个正整数

第三行为 个正整数

3.输出格式

一行, 一个整数表示答案。

4.样例输入

4 5
1 2 3 4
5 5 5 5

5.样例输出

3

这 5 张空白牌中, 拿 2 张写 1 , 拿 1 张写 2 , 这样每种牌的牌数就变为了

6.数据范围

对于 的数据, 保证 ;

对于 的数据, 保证

7.原题链接

​​卡牌​​

2.解题思路

，让我们去判断能否凑出 套牌，这个操作对我们来说并不难。所以我们可以考虑二分答案的做法，既然要二分那肯定得具有两段性，不难理解，如果我们可以凑出套牌，那么套牌也都是一定可以凑出来的,而并不一定可以凑出大于的套牌数。

  那么二分的​​check​​​判断函数我们该如何书写呢？显然要凑够套牌，我们需要使得每种类似的牌都有张，如果已经当前判断牌的类型的数量已经大于等于，则不需要使用空白牌补充。如果使用当前类型的牌数加上它最多可加上的空白牌数仍然小于,那么此时可以直接返回​​​false​​​了。如果当前牌类型允许补充空白牌的数量足够给我们进行补充到 ，那么我们让空白牌的数减去需要使用的数量，如果不够用了，那么也返回​​​false​​​，如果可以完成所有的牌的填充，则返回​​true​​。

的上限，以及的范围。的最大范围已经超出​​​int​​​，所以我们要使用​

上一篇： 2023-2024华为ICT大赛中国区 实践赛网络赛道 全国总决赛 理论部分真题-正确答案：C

下一篇： 我喜欢和你在一起，因为你充满正能量。