题目链接

[CQOI2010]扑克牌

题目描述

你有 种牌，第 种牌的数量为 。此外，你还有 张特殊的 Joker 牌。

一套牌有两种组合方式：

  1. 不使用 Joker 牌： 种牌各一张。
  2. 使用一张 Joker 牌：其他 种牌各一张。

你的任务是计算最多可以组成多少套牌。

解题思路

这是一个最大化问题，我们可以通过分析其性质来找到高效的解法。

1. 单调性分析

设我们可以组成的最多套牌数为 。

  • 如果我们可以组成 套牌，那么我们必然可以组成任意小于 套的牌。
  • 如果我们无法组成 套牌，那么我们也不可能组成任何大于 套的牌。

这种“可行性”关于“套牌数”的单调关系，是应用二分答案算法的典型特征。

2. 二分答案框架

我们可以不对牌的数量进行操作，而是直接对最终的答案——“套牌数”进行二分查找。

  • check(K) 函数： 二分答案的核心是编写一个 check(K) 函数，用于判断“是否可以组成 套牌？”

    要组成 套牌，意味着对于每一种牌 （从 到 ），我们最终都需要拥有 张。如果第 种牌的数量 不足 ，则必须用 Joker 牌来填补 的缺口。

    然而，题目规定一套牌最多只能使用一张 Joker。这带来了两个核心约束：

    1. Joker 总量约束：所有种类的牌的缺口总和，即我们需要的 Joker 总数，不能超过我们拥有的 Joker 数量 。

      • 约束 1:

    2. 每套牌的 Joker 约束：需要的 Joker 总数，也代表了需要进行“Joker 换普通牌”操作的总次数。因为每一套牌最多只能容纳一次这样的操作（即最多用一张 Joker），所以需要的 Joker 总数不能超过我们计划要组成的套牌数 。

      • 约束 2:

    只有当这两个约束同时满足时，check(K) 才返回 true。

  • 二分过程：

    • 我们设定一个二分查找的区间，如 。
    • 在循环中，取中点 。如果 check(mid) 为 true，说明 是一个可行的套数，我们尝试更多，故在右半区间搜索；如果为 false，说明 不可行，我们必须减少套数，故在左半区间搜索。

代码

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

using namespace std;

// 检查是否能组成 k 套牌
bool check(long long k, int n, long long m, const vector<long long>& c) {
    long long jokers_needed = 0;
    for (int i = 0; i < n; ++i) {
        if (c[i] < k) {
            jokers_needed += k - c[i];
        }
    }
    // 约束1：需要的joker不超过拥有的joker
    // 约束2：需要的joker不超过要组成的套数
    return jokers_needed <= m && jokers_needed <= k;
}

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

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

    long long left = 0, right = 1e9 + 5e8; // 一个足够大的上界
    long long ans = 0;

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

    cout << ans << endl;

    return 0;
}

import java.util.Scanner;

public class Main {
    // 检查是否能组成 k 套牌
    private static boolean check(long k, int n, long m, long[] c) {
        long jokersNeeded = 0;
        for (int i = 0; i < n; i++) {
            if (c[i] < k) {
                jokersNeeded += k - c[i];
            }
        }
        // 约束1：需要的joker不超过拥有的joker
        // 约束2：需要的joker不超过要组成的套数
        return jokersNeeded <= m && jokersNeeded <= k;
    }

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

        long left = 0, right = 1500000000L; // 一个足够大的上界
        long ans = 0;

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

def check(k, n, m, c):
    jokers_needed = 0
    for count in c:
        if count < k:
            jokers_needed += k - count
    
    # 约束1：需要的joker不超过拥有的joker
    # 约束2：需要的joker不超过要组成的套数
    return jokers_needed <= m and jokers_needed <= k

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

    left, right = 0, 10**9 + 5 * 10**8  # 一个足够大的上界
    ans = 0

    while left <= right:
        mid = (left + right) // 2
        if mid == 0:
            left = mid + 1
            continue
        if check(mid, n, m, c):
            ans = mid
            left = mid + 1
        else:
            right = mid - 1
    
    print(ans)

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法：二分答案。
  • 时间复杂度：，其中 是牌的种类数， 是二分查找的上界。check 函数每次调用需要 的时间，二分查找需要进行 次。
  • 空间复杂度：，用于存储 种牌的数量。