P16307 [蓝桥杯 2026 省 Java/Python 研究生组] 抓取卡牌

Link: https://www.luogu.com.cn/problem/P16307

题目描述

有 $n$ 种不同的卡牌，其中第 $i$ 种卡牌的基础价值为 $v_i$，数量为 $a_i$ 张。

你需要从这些卡牌中恰好选出 $X$ 张，组成自己的卡组。

对于同一种卡牌，随着你选取的数量增加，它后续的价值会下降。具体地，若某种基础价值为 $v$ 的卡牌已经被选了 $k$ 张，那么下一张这种卡牌的价值为：

$$\lfloor \frac{v}{k+1}\rfloor$$

$\lfloor x\rfloor$ 表示对 $x$ 向下取整，即不超过 $x$ 的最大整数。

也就是说：

• 选第 $1$ 张该种卡牌时，价值为 $\lfloor \frac{v}{1}\rfloor =v$；
• 选第 $2$ 张时，价值为 $\lfloor \frac{v}{2}\rfloor$；
• 选第 $3$ 张时，价值为 $\lfloor \frac{v}{3}\rfloor$；
• 依此类推。

每种卡牌至多只能选取 $a_i$ 张。

现在，请你计算：恰好选出 $X$ 张卡牌时，能够得到的最大总价值是多少。

输入格式

输入共三行。

第一行包含两个整数 $n,X$，分别表示卡牌种类数和需要选取的卡牌总数。

第二行包含 $n$ 个整数 $v_1,v_2,\dots ,v_n$，表示每种卡牌的基础价值。

第三行包含 $n$ 个整数 $a_1,a_2,\dots ,a_n$，表示每种卡牌可供选取的数量。

输出格式

输出一行一个整数，表示最大总价值。

输入输出样例 #1

输入 #1

6 6
1 1 2 3 4 5
1 2 1 2 3 4

输出 #1

18

说明/提示

【样例说明】

将所有可能选取的单张卡牌价值展开后，可得：

• 第 $1$ 种卡牌可贡献：$1$
• 第 $2$ 种卡牌可贡献：$1,0$
• 第 $3$ 种卡牌可贡献：$2$
• 第 $4$ 种卡牌可贡献：$3,1$
• 第 $5$ 种卡牌可贡献：$4,2,1$
• 第 $6$ 种卡牌可贡献：$5,2,1,1$

从中选出最大的 $6$ 个值：$5,4,3,2,2,2$，它们的和为：$5+4+3+2+2+2=18$，因此答案为 $18$。

【评测用例规模与约定】

对于 $50\%$ 的评测用例，$1\le n,X\le 5000$；

对于所有的评测用例，满足：$1\le n\le 2\times 10^5$，$0\le X,a_i\le 2\times 10^5$，$0\le v_i\le 10^9$。

保证所有卡牌总数不少于 $X$。

---

Solution

1. 题意

$n$ 种卡牌，第 $i$ 种初始时有 $a_i$ 张。同种卡牌被选择的次数越多，后续的价值会按照反比例下降，求最优的选卡方案。

2. 分析

由于每种卡牌的价值随选取数量增加而单调不增，因此可以将每种卡牌视为一个已经排好序的递减序列（$n$ 种卡牌那就是元素为序列的序列）。

题目要求从所有这些序列中选出全局最大的 $X$ 个值，可通过最大堆高效实现。

具体地说，对于每种卡牌 $i$，第 $1$ 张的价值一定是最大的，为 $v_i$。我们将所有 $a_i>0$ 的卡牌的首张价值以及张数作为一个二元状态组 $(v_i,i)$ 放入最大堆中。同时用一个数组 { k i } \{k_i\} {ki​} 记录第 $i$ 种卡牌当前已经选到了第几张。

最优的选卡，就是重复 $X$ 次下面的操作：

• 抽卡，也就是弹出堆顶元素（当前所有可选卡牌中价值最大的一张），将其价值累加到答案中，记录这张卡的标号 $j$。

• 该种卡牌的计数器 $k_j$ 加 $1$。如果 $k_j<a_j$，说明该种卡牌还有剩余，则计算下一张的价值 $\lfloor \frac{v_j}{k_j}\rfloor$ 并将此值移入堆中。

根据最大堆的性质，每次抽卡后，所有卡牌的价值会自动重新排布使得新的价值最大的卡牌编号及其价值“浮出水面”，因此顺着这个思路一定能得到最优解。

3. 代码

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n, X;
    if (!(cin >> n >> X)) return 0;

    vector<int> v(n), a(n);
    for (int i = 0; i < n; ++i)
    {
        cin >> v[i];
    }
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
    }

    vector<int> k(n, 1);
    priority_queue<pair<int, int>> pq;

    for (int i = 0; i < n; ++i)
    {
        if (a[i] > 0)
        {
            pq.emplace(v[i], i);
        }
    }

    long long ans = 0;
    for (int i = 0; i < X; ++i)
    {
        auto [val, idx] = pq.top();
        pq.pop();
        ans += val;
        k[idx]++;
        if (k[idx] <= a[idx])
        {
            pq.emplace(v[idx] / k[idx], idx);
        }
    }

    cout << ans << endl;
    return 0;
}