题解 | #[CQOI2010]扑克牌#

题目链接

扑克牌

题目描述

你有 $n$ 种不同类型的牌，第 $i$ 种牌的数量为 $c_i$ 。此外，你还有 $m$ 张万能的 Joker 牌。一套牌的组合方式如下：

不使用 Joker： $n$ 种牌各一张。
使用一张 Joker：一张 Joker 牌，加上剩下 $n-1$ 种类型的牌各一张。

每张牌最多只能用在一套牌里。请问你最多可以组成多少套牌？

输入:

第一行输入两个整数 $n$ 和 $m$ ，分别代表牌的种数和 Joker 的数量。
第二行输入 $n$ 个整数 $c_1, c_2, \dots, c_n$ ，代表每种牌的张数。

输出:

输出一个整数，代表最多可以组成的套牌数量。

解题思路

我们要求解的是“最多”可以组成多少套牌，这是一个典型的最优化问题。我们可以观察到一个关键的单调性：如果我们能组成 $x$ 套牌，那么我们必然也能组成 $x-1$ 套牌。这个性质表明，我们可以通过二分查找来高效地找到答案。

我们的任务是确定一个合适的查找范围，并设计一个 check(x) 函数来判断“是否可以组成 $x$ 套牌”。

check(x) 函数的设计：

假设我们想组成 $x$ 套牌。对于每一种牌型 $i$ （从 1 到 $n$ ），我们都需要 $x$ 张。我们手上有 $c_i$ 张。

如果 $c_i \ge x$ ，我们有足够的第 $i$ 种牌，不需要Joker。
如果 $c_i < x$ ，我们缺少 $x - c_i$ 张第 $i$ 种牌。这个缺口必须由 Joker 来填补。

所以，为了组成 $x$ 套牌，我们所需要的最少 Joker 数量等于所有牌型的缺口之和。令总缺口（即必须使用的 Joker 数量）为 $S = \sum_{i=1}^{n} \max(0, x - c_i)$ 。

现在，我们需要考虑题目给出的两个限制：

Joker 数量限制：我们使用的 Joker 总数 $S$ 不能超过我们拥有的 Joker 总数 $m$ 。因此，必须满足 $S \le m$ 。
每套牌的限制：规则规定，每一套牌最多只能使用一张 Joker。这意味着，我们组成的 $x$ 套牌，总共最多只能容纳 $x$ 张 Joker。因此，我们需要的 Joker 总数 $S$ 也不能超过 $x$ 。所以，必须满足 $S \le x$ 。

综上所述，当且仅当 $S \le m$ 且 $S \le x$ 时，我们才能成功组成 $x$ 套牌。我们的 check(x) 函数就基于这个逻辑。

二分查找流程：

设定一个足够大的查找范围，例如 low = 0，high 可以设为一个较大的数（如 $2 \cdot 10^9$ ，远大于任何可能的答案）。
在 [low, high] 范围内进行二分查找。对于每一个中间值 mid：
- 如果 check(mid) 为真，说明组成 mid 套牌是可行的，我们尝试寻找更多的套牌，即 low = mid + 1，并记录 mid 为一个可能的答案。
- 如果 check(mid) 为假，说明 mid 太大了，我们需要减少套牌数量，即 high = mid - 1。
二分查找结束后，记录的最后一个可行答案即为最大值。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

bool check(long long x, int n, long long m, const vector<int>& c) {
    if (x == 0) return true;
    long long jokers_needed = 0;
    for (int i = 0; i < n; ++i) {
        if (c[i] < x) {
            jokers_needed += x - c[i];
        }
    }
    return jokers_needed <= m && jokers_needed <= x;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    long long m;
    cin >> n >> m;
    vector<int> c(n);
    for (int i = 0; i < n; ++i) {
        cin >> c[i];
    }

    long long low = 0, high = 2000000000, ans = 0;
    while (low <= high) {
        long long mid = low + (high - low) / 2;
        if (check(mid, n, m, c)) {
            ans = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    cout << ans << endl;

    return 0;
}

import java.util.Scanner;

public class Main {
    public static boolean check(long x, int n, long m, int[] c) {
        if (x == 0) return true;
        long jokersNeeded = 0;
        for (int i = 0; i < n; i++) {
            if (c[i] < x) {
                jokersNeeded += x - c[i];
            }
        }
        return jokersNeeded <= m && jokersNeeded <= x;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long m = sc.nextLong();
        int[] c = new int[n];
        for (int i = 0; i < n; i++) {
            c[i] = sc.nextInt();
        }

        long low = 0, high = 2000000000, ans = 0;
        while (low <= high) {
            long mid = low + (high - low) / 2;
            if (check(mid, n, m, c)) {
                ans = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        System.out.println(ans);
    }
}

def check(x, n, m, c):
    if x == 0:
        return True
    jokers_needed = 0
    for i in range(n):
        if c[i] < x:
            jokers_needed += x - c[i]
    return jokers_needed <= m and jokers_needed <= x

def solve():
    n, m = map(int, input().split())
    c = list(map(int, input().split()))

    low, high = 0, 2 * 10**9 
    ans = 0
    
    while low <= high:
        mid = (low + high) // 2
        if check(mid, n, m, c):
            ans = mid
            low = mid + 1
        else:
            high = mid - 1
            
    print(ans)

solve()

算法及复杂度

算法：二分查找
时间复杂度： $\mathcal{O}(n \cdot \log V)$ ，其中 $V$ 是二分查找上界（本例中为 $2 \cdot 10^9$ ）。每次 check 函数需要 $\mathcal{O}(n)$ 的时间，二分查找的次数为 $\mathcal{O}(\log V)$ 。
空间复杂度： $\mathcal{O}(n)$ ，用于存储 $n$ 种牌的数量。