c++怎么用二分法解决这个问题这天 小明在整理他的卡牌。他一共有 nn 种卡牌 第 ii 种卡牌上印有正整数数 ii in1 nii∈1n 且第 ii 种卡牌 现有 a_ia i 张。而如果有 nn 张卡牌 其中每种卡牌各一张 那么这 nn 张卡牌可以被称为一 套牌。小明为了凑出尽可能多套牌 拿出了 mm 张空白牌 他可以在上面写上数 ii 将其当做第 ii 种牌来凑出套牌。然而小明觉得手写的

这个问题可以使用二分法来解决。

首先，我们定义一个函数check，用来判断给定的牌数是否能凑出至少m套牌。check函数的输入参数是一个整数x，表示手写的牌的张数。在check函数中，我们遍历每一种卡牌，计算需要多少张手写的牌才能凑出至少m套牌。如果需要的手写牌的张数不超过x，则说明x满足条件，返回true；否则返回false。

接下来，使用二分法在区间[0, max(b)]中搜索答案。初始时，左边界l=0，右边界r=max(b)。在每次循环中，计算中间值mid=(l+r)/2，并调用check函数判断mid是否满足条件。如果mid满足条件，说明答案在[mid+1, r]区间内，更新左边界l=mid+1；否则，答案在[l, mid-1]区间内，更新右边界r=mid-1。循环终止的条件是l>r，此时答案就是r。

最后，输出答案即可。

下面是具体的实现代码：

#include <iostream>
#include <vector>
using namespace std;

// 判断给定的牌数是否能凑出至少m套牌
bool check(int x, vector<int>& a, vector<int>& b, int m) {
    int cnt = 0;
    for (int i = 0; i < a.size(); i++) {
        int need = max(0, m * a[i] - b[i]);
        if (need > x) {
            return false;
        }
        cnt += need;
    }
    return cnt <= x;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }

    int l = 0, r = *max_element(b.begin(), b.end());
    int ans = 0;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (check(mid, a, b, m)) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    cout << ans << endl;

    return 0;
}

该算法的时间复杂度为O(log(max(b)) * n)，其中n为卡牌的种类数，max(b)为b数组中的最大值