第十三届蓝桥杯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​​​，所以我们要使用​​long long​​​，另外的最大范围是，而最大取到,能凑出的最大套牌数应该是,所以的上限一定不能设小了。

整体做法的时间复杂为:

3.Ac_code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=200010;

//二分答案
LL n,m;
int a[N],b[N];
bool check(int x){
    LL v=m;
    for(int i=1;i<=n;++i){
        //直接符合
        if(a[i]>=x) continue;
        //肯定不符合
        if(a[i]+b[i]<x) return false;
        if(a[i]+b[i]>=x&&v>=x-a[i]){
            v-=(x-a[i]);
        }else{
            return false;
        }
    }
    return true;
}
int main() 
{
    cin>>n>>m;
    for(int i=1;i<=n;++i) cin>>a[i];
    for(int i=1;i<=n;++i) cin>>b[i];
    int l=0,r=N*2;
    while(l<r){
        int mid=(l+r+1)>>1;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    cout<<r<<endl;
    return 0;
}