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

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

news 来源：原创 2024/5/17 20:22:16

CSDN话题挑战赛第2期
参赛话题：算法题解

1.卡牌

1.问题描述

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

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

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

2.输入格式

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

第二行为 $n$ 个正整数 $a_{1}, a_{2}, \ldots, a_{n}。$

第三行为 $n$ 个正整数 $b_{1}, b_{2}, \ldots, b_{n}。$

3.输出格式

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

4.样例输入

4 5
1 2 3 4
5 5 5 5

5.样例输出

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

6.数据范围

对于 $\%$ 的数据, 保证 $\leq 2000$ ;

对于 $\%$ 的数据, 保证 $\leq 2 \times 10^{5} ; a_{i}, b_{i} \leq 2 n ; m \leq n^{2}$ 。

7.原题链接

卡牌

2.解题思路

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

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

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

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

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