C++ 二分法解决卡牌套牌问题

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

首先，我们定义一个函数'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数组中的最大值。