P16307 [蓝桥杯 2026 省 Java/Python 研究生组] 抓取卡牌Link: https://www.luogu.com.cn/problem/P16307题目描述有n nn种不同的卡牌其中第i ii种卡牌的基础价值为v i v_ivi数量为a i a_iai张。你需要从这些卡牌中恰好选出X XX张组成自己的卡组。对于同一种卡牌随着你选取的数量增加它后续的价值会下降。具体地若某种基础价值为v vv的卡牌已经被选了k kk张那么下一张这种卡牌的价值为⌊ v k 1 ⌋ \left\lfloor \frac{v}{k 1} \right\rfloor⌊k1v⌋⌊ x ⌋ \lfloor x \rfloor⌊x⌋表示对x xx向下取整即不超过x xx的最大整数。也就是说选第1 11张该种卡牌时价值为⌊ v 1 ⌋ v \left\lfloor \frac{v}{1} \right\rfloor v⌊1v⌋v选第2 22张时价值为⌊ v 2 ⌋ \left\lfloor \frac{v}{2} \right\rfloor⌊2v⌋选第3 33张时价值为⌊ v 3 ⌋ \left\lfloor \frac{v}{3} \right\rfloor⌊3v⌋依此类推。每种卡牌至多只能选取a i a_iai张。现在请你计算恰好选出X XX张卡牌时能够得到的最大总价值是多少。输入格式输入共三行。第一行包含两个整数n , X n, Xn,X分别表示卡牌种类数和需要选取的卡牌总数。第二行包含n nn个整数v 1 , v 2 , … , v n v_1, v_2, \dots, v_nv1,v2,…,vn表示每种卡牌的基础价值。第三行包含n nn个整数a 1 , a 2 , … , a n a_1, a_2, \dots, a_na1,a2,…,an表示每种卡牌可供选取的数量。输出格式输出一行一个整数表示最大总价值。输入输出样例 #1输入 #16 6 1 1 2 3 4 5 1 2 1 2 3 4输出 #118说明/提示【样例说明】将所有可能选取的单张卡牌价值展开后可得第1 11种卡牌可贡献1 11第2 22种卡牌可贡献1 , 0 1, 01,0第3 33种卡牌可贡献2 22第4 44种卡牌可贡献3 , 1 3, 13,1第5 55种卡牌可贡献4 , 2 , 1 4, 2, 14,2,1第6 66种卡牌可贡献5 , 2 , 1 , 1 5, 2, 1, 15,2,1,1从中选出最大的6 66个值5 , 4 , 3 , 2 , 2 , 2 5, 4, 3, 2, 2, 25,4,3,2,2,2它们的和为5 4 3 2 2 2 18 543222 1854322218因此答案为18 1818。【评测用例规模与约定】对于50 % 50\%50%的评测用例1 ≤ n , X ≤ 5000 1 \le n, X \le 50001≤n,X≤5000对于所有的评测用例满足1 ≤ n ≤ 2 × 10 5 1 \le n \le 2 \times 10^51≤n≤2×1050 ≤ X , a i ≤ 2 × 10 5 0 \le X, a_i \le 2 \times 10^50≤X,ai≤2×1050 ≤ v i ≤ 10 9 0 \le v_i \le 10^90≤vi≤109。保证所有卡牌总数不少于X XX。Solution1. 题意n nn种卡牌第i ii种初始时有a i a_iai张。同种卡牌被选择的次数越多后续的价值会按照反比例下降求最优的选卡方案。2. 分析由于每种卡牌的价值随选取数量增加而单调不增因此可以将每种卡牌视为一个已经排好序的递减序列n nn种卡牌那就是元素为序列的序列。题目要求从所有这些序列中选出全局最大的X XX个值可通过最大堆高效实现。具体地说对于每种卡牌i ii第1 11张的价值一定是最大的为v i v_ivi。我们将所有a i 0 a_i0ai0的卡牌的首张价值以及张数作为一个二元状态组( v i , i ) (v_i,i)(vi,i)放入最大堆中。同时用一个数组{ k i } \{k_i\}{ki}记录第i ii种卡牌当前已经选到了第几张。最优的选卡就是重复X XX次下面的操作抽卡也就是弹出堆顶元素当前所有可选卡牌中价值最大的一张将其价值累加到答案中记录这张卡的标号j jj。该种卡牌的计数器k j k_jkj加1 11。如果k j a j k_ja_jkjaj说明该种卡牌还有剩余则计算下一张的价值⌊ v j k j ⌋ \left \lfloor \dfrac{v_{j}}{k_{j}} \right \rfloor⌊kjvj⌋并将此值移入堆中。根据最大堆的性质每次抽卡后所有卡牌的价值会自动重新排布使得新的价值最大的卡牌编号及其价值“浮出水面”因此顺着这个思路一定能得到最优解。3. 代码#includebits/stdc.husingnamespacestd;intmain(){intn,X;if(!(cinnX))return0;vectorintv(n),a(n);for(inti0;in;i){cinv[i];}for(inti0;in;i){cina[i];}vectorintk(n,1);priority_queuepairint,intpq;for(inti0;in;i){if(a[i]0){pq.emplace(v[i],i);}}longlongans0;for(inti0;iX;i){auto[val,idx]pq.top();pq.pop();ansval;k[idx];if(k[idx]a[idx]){pq.emplace(v[idx]/k[idx],idx);}}coutansendl;return0;}
