模拟【打牌游戏】

Problem - B - Codeforces鲍勃喜欢在手机上玩一款有趣的塔防游戏。在游戏里他需要出牌来击败对手有 n 张牌排成一个队列称为牌组。在任意时刻鲍勃只能打出牌组中前 k 个位置里的牌。每一轮鲍勃会选择前 k 个位置中的一张牌将其从牌组中移出并打出然后把这张牌放回牌组末尾。换句话说每一轮都会从队列的前 k 个元素中选一个移到队列末尾它后面的所有元素都向前移动一位。其中有一张牌是胜利条件牌鲍勃想尽可能多次打出它。但每张牌都有对应的消耗第 i 张牌初始在第 i 位每次被打出时会消耗鲍勃 ai​ 点能量。所有打出的牌的总消耗不能超过 m。胜利条件牌初始在队列的第 p 个位置。请你求出在总消耗不超过 m 的前提下胜利条件牌最多能被打出多少次。输入每个测试文件包含多组测试用例。第一行一个整数 t1≤t≤5000表示测试用例数量。每组测试用例第一行包含四个整数 n,k,p,mn牌的数量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, ans0, df, s0, o0; cin n k p m; // 第一阶段读取分离胜利牌和其前方的挡路牌 // 读取前p张牌包含胜利牌胜利牌在a[p-1]位置 for(int i0;ip;i){ cina[i]; // 读取前p张牌 if(ip-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 i0; i p - k; i) { ans a[i]; } // 首次总成本 挡路牌最小成本 胜利牌自身成本 ans df; } // 判断首次是否能打出胜利牌 if(ans m) { o; // 能打出则次数1 } // 第二阶段读取补充剩余牌覆盖原胜利牌位置 // 从a[p-1]开始读取覆盖原胜利牌位置数组中只剩非胜利牌 for(int ip-1; i n-1; i) { cina[i]; } // 关键对所有非胜利牌排序找循环时最小消耗的附加牌 sort(a, a n - 1); // 计算循环打出胜利牌的成本 int b n - k; // 循环时需打(n-k)张附加牌才能让胜利牌回到前k位 s df; // 循环成本基础胜利牌自身消耗 // 选所有非胜利牌中最小的b张累加附加成本 for(int i0; i b; i) { s a[i]; } // 计算总次数首次次数 剩余能量可支撑的循环次数 // 剩余能量 总能量 - 首次成本除以循环成本得到循环次数 o (m - ans) / s; // 输出每组测试用例的结果 cout o endl; } return 0; }数组复用第一阶段数组存 “胜利牌 前方挡路牌”读取后立即用df保存胜利牌避免后续覆盖丢失第二阶段从a[p-1]开始读取剩余牌覆盖原胜利牌位置让数组仅保留 “非胜利牌”无需额外开数组。局部排序第一次排序仅排 “胜利牌前方的挡路牌”精准匹配 “首次成本” 计算需求第二次排序仅排 “所有非胜利牌”精准匹配 “循环成本” 计算需求相比全局排序减少无效计算效率更高。贪心策略首次成本选最小的p-k张挡路牌最小化首次附加成本循环成本选最小的n-k张附加牌最小化每次循环的附加成本最终通过 “最小成本” 最大化胜利牌打出次数。