蓝桥杯2022国赛《卡牌》题解（纯记录，欢迎指正）

整数二分

解题思路

首先，我们来理解这个题目的题意：

问题描述：你有n种卡牌和m张空白卡牌，每种卡牌初始时有a[i]张，并且最多可以使用b[i]张空白卡牌来增加它的数量，现在问在最优分配下，所有卡牌的最小值的最大可能值为多少？

正如样例说明中提到的：这 5 张空白牌中, 拿 2 张写 1 , 拿 1 张写 2 , 这样每种牌的牌数就变为了 3,3,3,4, 可以凑出 3 套牌, 剩下 2 张空白牌不能再帮助小明凑出一套。样例的最优分配使得卡牌的最小值的最大可能值为3。

理解了题目的意思之后，我们先来想想这道题目的暴力解法：
要暴力解决卡牌问题，我们可以尝试枚举所有可能的答案 x（最多能凑出的套数）。
    1.确定x的范围：
        x的最小值是所有a[i]的最小值
        x的最大值是所有a[i]+b[i]的最大值
        因此我们得到了x的可能范围
    2.接下来，我们从大到小枚举x（因为要找到最大可能x）
        对于每个x，计算要多少张空白牌才能使得所有的a[i]>=x
        如果a[i]>=x，则不需要空白牌来补充
        如果a[i]<x，那么需要x-a[i]张空白牌，但是x-a[i]不能大于b[i]（因为每种牌最多补充b[i]张）
        在遍历的过程中，计算一共需要的空白牌数量k
        如果k<=m，则x可行，就得到了答案
        如果k>m，那么当前x不可行，继续遍历x的过程
    3.暴力算法的时间复杂度分析：
        x的范围是max(a[i]+b[i])-min(a[i])
        对于每个x，需要O(n)的时间计算k
        所以，总的时间复杂度是O( (max(a[i]+b[i])-min(a[i]))×n )
        题目给出的数据范围是
        n≤2×1e5
        a[i],b[i]≤2n
        m≤n^2
        所以a[i],b[i]<=4×1e5
        max(a[i]+b[i])-min(a[i])<=8×1e5
        最坏的时间复杂度是8×1e5×2×1e5=16×1e10
        很明显，暴力做法会超时，所以我们要思考用什么算法来优化我们的时间复杂度。

暴力代码实现：

#include<iostream>
#include<algorithm>
using namespace std;
int n;
long long m;
const int N = 200010;
int a[N];
int b[N];
int force() {
    int min_a = a[1], max_a_plus_b = a[1] + b[1];
    for (int i = 1; i <= n; i++) 
    {
        min_a = min(min_a, a[i]);
        max_a_plus_b = max(max_a_plus_b, a[i] + b[i]);
    }
    for (int x = max_a_plus_b; x >= min_a; x--) 
    {
        long long k = 0;
        bool flag = true;
        for (int i = 1; i <= n; i++) 
        {
            if (a[i] >= x) continue;
            if (x - a[i] > b[i]) 
            { 
                flag = false; break; 
            }
            else
            {
                k += (x - a[i]);
            }
        }
        if (flag && k <= m) return x;
    }
    return min_a;
}
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];
    }
    cout << force() << endl;
    return 0;
}

算法思路分析：
我们重新来观察这个问题，问题问的是在空白牌的最优分配下，所有卡牌最小值的最大可能值是多少。
这道题关键在于：
    单调性：如果答案可以是x，那么比x小的值也一定可以满足条件，反之，比x大的值一定不满足条件。
    求最大值：我们需要找到最大的x，使得存在一种分配方式满足条件
这种求最大或者最小的满足某种条件的值的问题，通常可以考虑用二分的算法来优化寻找答案的时间复杂度。
二分问题的共同点是：
    1.求最大/最小的满足条件的值
    2.答案具有单调性
如果看过y总算法基础课的同学应该都知道二分的两种模板，这里我们直接使用模板

代码实现：

#include<iostream>
using namespace std;
int n;
long long m;
const int N=200010;
int a[N];
int b[N];
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];
    }
    for(int i=1;i<n;i++)
    {
        if(a[i]+b[i]>max)
        {
            max=a[i]+b[i];
        }
    }
    int l=0,r=max;
    while(l<r)
    {
        int mid=l+r+1>>1;
        long long k=0;
        bool flag=1;
        for(int i=1;i<=n;i++)
        {
            if(mid<=a[i])
            {
                continue;
            }
            if(mid-a[i]>b[i])
            {
                flag=0;
                break;
            }
            else
            {
                k+=mid-a[i];
            }
        }
        if(k>m)
        {
            flag=0;
        }
        if(flag==1)
        {
            l=mid;
        }
        else if(flag==0)
        {
            r=mid-1;
        }
    }
    cout<<l<<endl;
    return 0;
}