扑克牌

GitHub跳转原题关系图返回列表

二分答案 + 可行性判定(贪心)。二分能整理出多少副牌,计算所需特殊牌数量验证可行性。

OJ: roj

题目 ID: 5007

难度:普及+/提高-

标签:二分答案贪心

创建: 2026-10-08 09:07

更新: 2026-10-08 09:07

形式化题目

给定 nn 种普通扑克牌,每种各有 a1,a2,…,ana_1, a_2, \ldots, a_n 张,以及 bb 张特殊牌。你需要用这些牌拼出尽量多的套牌。一套牌要么包含 nn 种普通牌各一张,要么包含 n−1n-1 种普通牌各一张加上 11 张特殊牌。求最多能拼出多少套牌。

本题测试数据系自造数据,出题意图可能与官方原题(如一本通 1671 或 ybtoj)存在细微偏差,但本题解能通过所有数据。

正解

思路

我们要最大化拼出的套牌数,由于“判断能否拼出 xx 套牌”比“直接求出最多套牌数”容易,且答案具有单调性(若能拼出 xx 套,必然能拼出 x−1x-1 套),因此可以使用二分答案。

假设我们要验证能否拼出 xx 套牌:

  1. 对于每一种普通牌 ii,如果它原有的张数 ai<xa_i < x,那么不足的部分 x−aix - a_i 必须用特殊牌来顶替。
  2. 我们把所有种类需要的特殊牌数量累加起来,记为 need。如果 need > b,说明特殊牌不够用,拼不出 xx 套。
  3. 还有一个隐藏限制:因为每套牌最多只能用 11 张特殊牌,所以在拼这 xx 套牌的过程中,至多能消耗 xx 张特殊牌(实际上,对某一种牌需要的顶替次数也不能超过 xx,但因为 ai≥0a_i \ge 0,所以 x−ai≤xx - a_i \le x,单种牌的顶替不会超过 xx)。因此,如果 need > x,即所需的特殊牌总数超过了总套数,根据抽屉原理,必有一套牌用了至少 22 张特殊牌,这是不合法的。
  4. 综合以上两点,如果 need <= b 且在累加过程中始终有 need <= x,说明可以拼出 xx 套牌。

二分的上界:所有普通牌加上特殊牌的总数量为 sum=b+∑i=1naisum = b + \sum_{i=1}^{n} a_i。每套牌需要 nn 张,理论上的绝对最大套牌数为 sum/nsum / n,可以设二分上界为 (sum+b)/n+1(sum + b) / n + 1 确保足够大,下界为 00。

代码

python
import sys

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    n = int(input_data[0])
    b = int(input_data[1])
    a = [int(x) for x in input_data[2:]]
    
    sum_a = sum(a)
    lo = 0
    hi = (sum_a + b) // n + 1
    
    ans = 0
    while lo <= hi:
        mid = (lo + hi) // 2
        need = 0
        possible = True
        for cards in a:
            if cards < mid:
                need += mid - cards
                if need > mid:
                    possible = False
                    break
        if possible and need <= b:
            ans = mid
            lo = mid + 1
        else:
            hi = mid - 1
            
    print(ans)

if __name__ == '__main__':
    solve()
cpp
#include <iostream>
#include <vector>

using namespace std;

bool check(long long x, int n, long long b, const vector<int>& a) {
    long long need = 0;
    for (int i = 0; i < n; ++i) {
        if (a[i] < x) {
            need += x - a[i];
            if (need > x) return false;
        }
    }
    return need <= b;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    long long b;
    if (!(cin >> n >> b)) return 0;
    vector<int> a(n);
    long long sum = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        sum += a[i];
    }
    
    long long lo = 0, hi = (sum + b) / n + 1;
    long long ans = 0;
    while (lo <= hi) {
        long long mid = lo + (hi - lo) / 2;
        if (check(mid, n, b, a)) {
            ans = mid;
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    
    cout << ans << "\n";
    return 0;
}

复杂度

  • 时间复杂度:计算总和需 O(n)\mathcal{O}(n),二分答案范围在 [0,∑ai+bn+1][0, \frac{\sum a_i + b}{n} + 1] 内,最多循环约 log⁡2(max⁡(ai)+b)≈40\log_2(\max(a_i) + b) \approx 40 次。每次 check 需要遍历 nn 个数,时间为 O(n)\mathcal{O}(n)。总时间复杂度为 O(nlog⁡(max⁡(ai)+b))\mathcal{O}(n \log (\max(a_i) + b))。对于 n≤106n \le 10^6 足以在规定时限内通过。
  • 空间复杂度:需要数组存储每种普通牌的数量,空间复杂度为 O(n)\mathcal{O}(n)。

总结

经典二分答案题目。难点主要在于想到第二个限制条件(每副牌最多用一张特殊牌,从而限制了总的代替次数不能超过要整理的套牌数)。对于极值最优化且正向难以贪心计算的问题,转化为判定问题并结合二分是一种非常基础且重要的思路。