第十三届蓝桥杯C++B组国赛C题——卡牌 (AC)

今天药忘吃喽~ 2023-09-28 23:11 3阅读 0赞

[CSDN话题挑战赛第2期][CSDN_2]  
参赛话题：[算法题解][Link 1]

#### 目录 ####

*  1.卡牌
 *   *  1.问题描述
     *  2.输入格式
     *  3.输出格式
     *  4.样例输入
     *  5.样例输出
     *  6.数据范围
     *  7.原题链接
 *  2.解题思路
 *  3.Ac\_code

## 1.卡牌 ##

### 1.问题描述 ###

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

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

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

### 2.输入格式 ###

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

第二行为  n n n 个正整数  a 1 , a 2 , … , a n 。 a\_\{1\}, a\_\{2\}, \\ldots, a\_\{n\}。 a1,a2,…,an。

第三行为  n n n 个正整数  b 1 , b 2 , … , b n 。 b\_\{1\}, b\_\{2\}, \\ldots, b\_\{n\}。 b1,b2,…,bn。

### 3.输出格式 ###

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

### 4.样例输入 ###

4 5  
1 2 3 4  
5 5 5 5

### 5.样例输出 ###

这 5 张空白牌中, 拿 2 张写 1 , 拿 1 张写 2 , 这样每种牌的牌数就变为了  3 , 3 , 3 , 4 3,3,3,4 3,3,3,4 可以凑出 3 套牌, 剩下 2 张空白牌不能再帮助小明凑出一套。

### 6.数据范围 ###

对于  30 % 30 \\% 30% 的数据, 保证  n ≤ 2000 n \\leq 2000 n≤2000;

对于  100 % 100 \\% 100% 的数据, 保证  n ≤ 2 × 1 0 5 ; a i , b i ≤ 2 n ; m ≤ n 2 n \\leq 2 \\times 10^\{5\} ; a\_\{i\}, b\_\{i\} \\leq 2 n ; m \\leq n^\{2\} n≤2×105;ai,bi≤2n;m≤n2 。

### 7.原题链接 ###

[卡牌][Link 2]

## 2.解题思路 ##

从题意出发，发现想直接求出答案，并没有一个很高效的办法，但如果给定我们一个  x x x ，让我们去判断能否凑出  x x x 套牌，这个操作对我们来说并不难。所以我们可以考虑**二分答案**的做法，既然要二分那肯定得具有两段性，不难理解，如果我们可以凑出 x x x套牌，那么 \[ 1 , x − 1 \] \[1,x-1\] \[1,x−1\]套牌也都是一定可以凑出来的,而并不一定可以凑出大于 x x x的套牌数。

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

另外一个需要注意的点是 r r r的上限，以及 m m m的范围。 m m m的最大范围已经超出`int`，所以我们要使用`long long`，另外 n n n的最大范围是 2 × 1 0 5 2×10^5 2×105，而 m m m最大取到 n 2 n^2 n2,能凑出的最大套牌数应该是 2 n 2n 2n,所以 r r r的上限一定不能设小了。

整体做法的时间复杂为: O ( n l o g n ) O(nlogn) O(nlogn)

## 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;
    }

[CSDN_2]: https://marketing.csdn.net/p/7b6697fd9dd3795a268d1a6f2fe75012
[Link 1]: https://activity.csdn.net/creatActivity?id=10221
[Link 2]: https://www.lanqiao.cn/problems/2191/learning/