蓝桥云客卡牌

2.卡牌 - 蓝桥云课

卡牌

问题描述

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

输入格式

输入共3行，第一行为两个正整数n, m。
第二行为n个正整数a_1, a_2, ..., a_n。
第三行为n个正整数b_1, b_2, ..., b_n。

输出格式

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

样例输入

4 5
1 2 3 4
5 5 5 5

样例输出

样例说明

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

评测用例规模与约定

对于30%的数据，保证n < 2000；
对于100%的数据，保证n ≤ 2 × 10^5；a_i, b_i ≤ 2n；m ≤ n^2。

运行限制

最大运行时间：1s
最大运行内存：512M

总通过次数：3448 | 总提交次数：4060 | 通过率：84.9%

难度：中等标签：2022 国赛二分

思路：

贪心思路，能凑出一组排就凑，a数组不够就用b数组和m的，如果凑不出来就结束了。
代码如下：

#include<iostream>
#include<algorithm>
#include<iomanip> 
using namespace std;
typedef long long ll;
const ll N = 2e5+10;
ll n,a[N],b[N],m;
ll cnt = 0;
int main()
{cin >> n >> m;for(ll i = 1 ; i <= n ; i++)cin >> a[i];for(ll i = 1 ; i <= n ; i++)cin >> b[i];bool found = true;;while(1){for(ll i = 1 ; i <= n ; i++){if(a[i] > 0){a[i]--;	}else if(b[i] > 0 && m > 0){b[i]--;m--;}else{found = false;break;}}if(found)cnt++;elsebreak;}cout << cnt;return 0;
}

思路：
二分枚举凑出卡牌的次数，然后跟贪心思维的过程类似，都是要模拟这个枚举的组数是否能成功。

代码如下：

#include<iostream>
#include<algorithm>
#include<iomanip> 
using namespace std;
typedef long long ll;
const ll N = 2e5+10;
ll n,a[N],b[N],m;
ll sum = 0;
bool check(ll x)
{ll p = m;for(ll i = 1 ; i <= n ; i++){if(a[i] >= x)continue;else if(a[i] + b[i] < x)//可使用凑数的牌都不够直接return false； return false;else if(a[i] + b[i] >= x && p > 0){p = p - ( b[i] - ((a[i] + b[i]) - x));}elsereturn false;}return true;
}
int main()
{cin >> n >> m;for(ll i = 1 ; i <= n ; i++){cin >> a[i];sum += a[i];	}for(ll i = 1 ; i <= n ; i++)cin >> b[i];ll l = 0,r = 2*N;while(l + 1 != r){ll mid = (l + r)/2;if(check(mid)){l = mid;}else{r = mid;}}cout << l;return 0;
}