模拟【打牌游戏】

ysa051030

833人浏览 · 2026-03-16 19:40:18

ysa051030 · 2026-03-16 19:40:18 发布

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

有 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。
第二个测试用例：可以打任意一张牌。最优策略就是只打胜利牌，它消耗 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;
}