这天，小明在整理他的卡牌。 他一共有 n 种卡牌，第 i 种卡牌上印有正整数数 i(i ∈ [1, n])，且第 i 种卡牌 现有 ai 张。 而如果有 n 张卡牌，其中每种卡牌各一张，那么这 n 张卡牌可以被称为一 套牌。小明为了凑出尽可能多套牌，拿出了 m 张空白牌，他可以在上面写上数 i，将其当做第 i 种牌来凑出套牌。然而小明觉得手写的牌不太美观，决定第 i 种牌最多手写 bi 张。 请问小明最多能凑出多少套牌？ 输入格式 输入共 3 行，第一行为两个正整数 n, m。 第二行为 n 个正整数 a1, a2, ..., an。 第三行为 n 个正整数 b1, b2, ..., bn。 输出格式 一行，一个整数表示答案

这是一道算法题，可以使用二分查找算法解决。

具体实现过程为，将可以凑成多少套牌视为搜索的答案，设定二分的区间为 [0, 4n+1]，每次检查当前的答案是否可行，即对于每个卡牌，如果将手写的牌都用来增加该卡牌的数量依然无法保证凑出的套牌数量不小于当前答案，或者剩余的手写牌数量不足以将该卡牌增加到答案数量，那么当前答案就不可行。最终找到最大可行的答案即可。

具体代码实现可以参考上述的 C++ 代码。

相关问题

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

可以使用贪心算法解决这个问题。首先将每种卡牌按照剩余数量从小到大排序，然后从剩余数量最少的卡牌开始尽可能地凑牌。当一个卡牌的数量用完后，就从下一个剩余数量最少的卡牌开始凑牌，直到所有卡牌都用完为止。

具体实现过程如下：

1. 将卡牌按照剩余数量从小到大排序。
2. 初始化套牌数为0。
3. 从剩余数量最少的卡牌开始遍历：
1. 如果该卡牌数量已经用完，则跳过该卡牌。
2. 否则，尽可能地将空白牌补全为该卡牌，直到空白牌用完或该卡牌数量用完为止，同时更新套牌数。
4. 返回套牌数。

代码实现如下：

def max_sets(n, a, m, b):
    # 将卡牌按照剩余数量从小到大排序
    cards = sorted([(i, a[i]) for i in range(n)], key=lambda x: x[1])
    # 初始化套牌数为0
    sets = 0
    # 遍历卡牌
    for i in range(n):
        # 如果该卡牌数量已经用完，则跳过该卡牌
        if cards[i][1] == 0:
            continue
        # 尽可能地将空白牌补全为该卡牌，直到空白牌用完或该卡牌数量用完为止
        for j in range(m):
            if b[j] and b[j] >= cards[i][0]:
                b[j] = 0
                cards[i] = (cards[i][0], cards[i][1] - 1)
                sets += 1
    # 返回套牌数
    return sets

时间复杂度为 O(nm)，其中 n 是卡牌种数，m 是空白牌数量。

c++ 小明参加一个比赛，规则是：每组卡牌有十张且点数为 1 到 10，现有 n 组卡牌，选手要在 n 组卡牌中，每组抽取一张，共抽 n 张；若 n 张卡牌的总点数大于 k 则小明获胜，求小明获胜的概率有多大？ 输入 两个整数 n，k。

好的，下面是 C++ 实现：

#include <iostream>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;

    // 计算不满足条件的抽卡方案数
    long long not_win = 0;
    for (int i = 0; i <= n; i++) {
        long long coeff = ((i & 1) ? -1 : 1) * binomial(n, i);
        not_win += coeff * binomial(k - 10 * i + n - 1, n - 1);
    }

    // 计算获胜概率
    double win_prob = 1.0 - (double)not_win / pow(10, n);
    cout << win_prob << endl;

    return 0;
}

// 计算组合数 C(n, m)
long long binomial(int n, int m) {
    long long res = 1;
    for (int i = 1; i <= m; i++) {
        res = res * (n - i + 1) / i;
    }
    return res;
}

该程序中用到了 `binomial` 函数，用来计算组合数，可以使用递推公式 $C(n, m) = C(n-1, m) + C(n-1, m-1)$ 或者阶乘公式 $C(n, m) = n!/(m!(n-m)!)$ 来实现。这里采用了阶乘公式，但是为了避免溢出，使用了循环计算的方式，每次只乘一个数，并且在乘完后除以一个数，避免了中间结果超过 `long long` 范围的问题。