当前位置：首页 > news >正文

模拟【打牌游戏】

news 2026/3/26 19:08:35

Problem - B - Codeforces

鲍勃喜欢在手机上玩一款有趣的塔防游戏。在游戏里，他需要出牌来击败对手！

有 n 张牌排成一个队列，称为牌组。在任意时刻，鲍勃只能打出牌组中前 k 个位置里的牌。每一轮，鲍勃会选择前 k 个位置中的一张牌，将其从牌组中移出并打出，然后把这张牌放回牌组末尾。换句话说，每一轮都会从队列的前 k 个元素中选一个，移到队列末尾，它后面的所有元素都向前移动一位。

其中有一张牌是胜利条件牌，鲍勃想尽可能多次打出它。但每张牌都有对应的消耗：第 i 张牌（初始在第 i 位）每次被打出时，会消耗鲍勃 ai 点能量。所有打出的牌的总消耗不能超过 m。胜利条件牌初始在队列的第 p 个位置。

请你求出：在总消耗不超过 m 的前提下，胜利条件牌最多能被打出多少次。

输入

每个测试文件包含多组测试用例。第一行一个整数 t（1≤t≤5000），表示测试用例数量。

每组测试用例第一行包含四个整数 n,k,p,m：

n：牌的数量
k：每轮可选择的前 k 张牌
p：胜利条件牌的初始位置
m：总能量上限

第二行包含 n 个整数 a1,a2,…,an（1≤ai≤m），表示每张牌的消耗。

保证所有测试用例的 n 之和不超过 5000。

输出

对于每组测试用例，输出一行一个整数，表示胜利条件牌最多能被打出的次数。

输入样例

4 2 1 2 42 42 1 3 3 2 6 2 1 2 3 2 2 6 2 1 2 8 4 7 10 3 4 4 2 1 1 4 2

输出样例

0 6 2 1

样例说明

第一个测试用例：每轮只能打第一张牌，打出它就会耗尽所有能量。胜利牌是第二张，根本无法打出，答案为 0。
第二个测试用例：可以打任意一张牌。最优策略就是只打胜利牌，它消耗 1 点能量，总能量 6 点，最多打 6 次。
第三个测试用例：初始牌组为 [2,1, 2]（胜利牌标红）。按如下方式出牌：
- 打第一张 → 牌组变为 [1, 2, 2]
- 再打第一张 → 牌组变为 [2, 2, 1]
- 再打第一张 → 牌组变为 [2, 1, 2]
- 打第二张（胜利牌）→ 牌组变为 [2, 2, 1]过程中胜利牌被打出 2 次，总消耗恰好 6。可以证明无法打出更多次。
第四个测试用例：最多只能打出胜利牌 1 次，通过一直打第 4 张牌即可实现。

1. 问题本质

我们需要最大化胜利牌的打出次数，且总能量消耗不超过m。核心原则是：打出胜利牌的附加成本越小，能打的次数越多。

2. 关键观察

要打出胜利牌，必须让它进入牌组前k位；
每次打出任意牌后，该牌会移到队尾，因此打出胜利牌需要 “先处理挡路牌”；
最优策略：处理挡路牌时，永远选消耗最小的牌，以此最小化附加成本，为胜利牌留出更多能量。

3. 解法拆分

我们将问题拆分为两步计算：

首次打出胜利牌的最小成本：让胜利牌第一次进入前k位所需的最小能量；
循环打出胜利牌的成本：首次打出后，每次循环打出胜利牌的固定最小成本；
总次数 = 首次次数 + 剩余能量 ÷ 循环成本。

#include <bits/stdc++.h> using namespace std; int a[5001]; int main() { int t; cin >> t; while (t--) { // 遍历每组测试用例 // 变量定义（核心变量） // n:牌总数 k:每轮可打前k张 p:胜利牌初始位置 m:总能量 // ans:首次打出胜利牌的最小总成本 df:胜利牌单次消耗 // s:循环打出一次胜利牌的总成本 o:胜利牌总打出次数 int n, k, p, m, ans=0, df, s=0, o=0; cin >> n >> k >> p >> m; // 第一阶段读取：分离胜利牌和其前方的挡路牌 // 读取前p张牌（包含胜利牌，胜利牌在a[p-1]位置） for(int i=0;i<p;i++){ cin>>a[i]; // 读取前p张牌 if(i==p-1) df = a[i]; // 单独保存胜利牌消耗（后续会被覆盖，需提前存） } // 关键：仅对胜利牌前方的p-1张牌排序（找最小消耗的挡路牌） // 胜利牌已用df保存，无需参与排序 sort(a, a + p - 1); // 计算首次打出胜利牌的最小成本 if(k >= p) { // 情况1：胜利牌初始就在前k位，无需打挡路牌，成本仅为胜利牌自身 ans = df; } else { // 情况2：胜利牌不在前k位，需打(p-k)张挡路牌才能让它进入前k位 // 选前p-1张中最小的(p-k)张，累加附加成本 for(int i=0; i < p - k; i++) { ans += a[i]; } // 首次总成本 = 挡路牌最小成本 + 胜利牌自身成本 ans += df; } // 判断首次是否能打出胜利牌 if(ans <= m) { o++; // 能打出则次数+1 } // 第二阶段读取：补充剩余牌，覆盖原胜利牌位置 // 从a[p-1]开始读取（覆盖原胜利牌位置），数组中只剩非胜利牌 for(int i=p-1; i < n-1; i++) { cin>>a[i]; } // 关键：对所有非胜利牌排序（找循环时最小消耗的附加牌） sort(a, a + n - 1); // 计算循环打出胜利牌的成本 int b = n - k; // 循环时，需打(n-k)张附加牌才能让胜利牌回到前k位 s = df; // 循环成本基础：胜利牌自身消耗 // 选所有非胜利牌中最小的b张，累加附加成本 for(int i=0; i < b; i++) { s += a[i]; } // 计算总次数：首次次数 + 剩余能量可支撑的循环次数 // 剩余能量 = 总能量 - 首次成本，除以循环成本得到循环次数 o += (m - ans) / s; // 输出每组测试用例的结果 cout << o << endl; } return 0; }