UVa 402 M*A*S*H

题目描述M*A*S*H\texttt{M*A*S*H}M*A*S*H题目描述了一个彩票淘汰游戏。有NNN个人排成一列编号从111到NNN。主持人有一叠牌每张牌上有一个数字111到111111之间。淘汰过程如下从队伍的第一个人开始按顺序报数1,2,3,…1, 2, 3, \dots1,2,3,…。当报数达到当前牌的数值时该位置的人被淘汰出列。淘汰后从下一个人开始重新从111报数。当队伍末尾被报完后无论最后报到了哪个数字都取下一张牌然后从队伍剩余的第一个人开始继续从111报数。重复上述过程直到只剩下XXX个人为止这XXX个人就是幸运的“回家”人选。如果202020张牌用完时剩下的人数仍多于XXX则所有剩余的人都是幸运的。给定NNN、XXX和202020张牌的数字需要输出所有幸运位置即最终剩余的人的原始编号。输入格式输入包含多组数据每组数据占一行。每行包含222222个整数第111个整数NNN1≤N≤501 \le N \le 501≤N≤50表示参与彩票的人数。第222个整数XXX1≤X≤N1 \le X \le N1≤X≤N表示幸运位置的数量。接下来的202020个整数表示牌堆中从上到下的202020张牌的数值111到111111之间。输入以文件结束符EOF\texttt{EOF}EOF终止。输出格式对于每组数据首先输出一行Selection #A其中AAA是当前数据的序号从111开始计数。下一行输出所有幸运位置的编号按升序排列以空格分隔。每组数据输出后跟一个空行。样例输入10 2 3 5 4 3 2 9 6 10 10 6 2 6 7 3 4 7 4 5 3 2 47 6 11 2 7 3 4 8 5 10 7 8 3 7 4 2 3 9 10 2 5 3输出Selection #1 1 8 Selection #2 1 3 16 23 31 47题目分析本题的核心是实现一个循环淘汰过程需要模拟报数和淘汰的完整流程。由于N≤50N \le 50N≤50可以直接使用数组或链表进行模拟。关键点在于淘汰规则是“报数到kkk则淘汰”其中kkk是当前牌的值。每淘汰一个人后重新从111开始报数。当队伍末尾被报完后取下一张牌从队伍第一个人继续。如果202020张牌用完仍未淘汰到只剩XXX人则剩余所有人都是幸运的。模拟方法的选择由于NNN很小可以使用一个数组表示队伍中的人用000或负值标记已被淘汰的人。每次遍历数组跳过已淘汰的人累计报数达到当前牌值时淘汰该位置。这种方法的时间复杂度为O(剩余人数×淘汰次数)O(\text{剩余人数} \times \text{淘汰次数})O(剩余人数×淘汰次数)最坏情况下约为O(N2)O(N^2)O(N2)对于N≤50N \le 50N≤50完全可行。循环与边界处理当报数到达队伍末尾时需要根据当前报到的数字决定下一步如果恰好有人在最后一个位置被淘汰则从队伍第一个人重新开始。否则记录当前报到的数字下一轮从队伍第一个人继续累加。更简单的做法是线性扫描每次从头遍历整个数组累计有效人数达到目标值即淘汰然后重新扫描。这种方法虽然看起来重复扫描很多次但由于NNN很小完全可行。解题思路步骤一读取输入每组数据包含222222个整数可以直接使用istringstream\texttt{istringstream}istringstream从一行中解析所有整数。将NNN和XXX分别存储将接下来的202020个数存入队列queueint cards\texttt{queueint cards}queueint cards中以便按顺序取出使用。步骤二初始化人员数组使用vectorint person\texttt{vectorint person}vectorint person存储初始编号可以使用iota(person.begin(), person.end(), 1)\texttt{iota(person.begin(), person.end(), 1)}iota(person.begin(), person.end(), 1)快速填充111到NNN。标记淘汰的方式可以将其值设为000。步骤三模拟淘汰过程设remaining\textit{remaining}remaining为当前剩余人数初始为NNN。当remainingX\textit{remaining} XremainingX且牌堆非空时取出一张牌其值为token\textit{token}token。从头扫描数组person\textit{person}person跳过值为000的人。维护一个计数器counter\textit{counter}counter每遇到一个未被淘汰的人counter\textit{counter}counter加111。当countertoken\textit{counter} \textit{token}countertoken时淘汰当前位置的人设为000remaining\textit{remaining}remaining减111然后将counter\textit{counter}counter重置为000。如果在本次扫描中remaining\textit{remaining}remaining降到了XXX立即跳出循环不再使用剩余的牌。如果扫描完整个数组后remaining\textit{remaining}remaining仍未降到XXX继续下一轮扫描使用下一张牌。注意每次淘汰后继续从当前位置的下一个人开始报数不用重置扫描位置到开头。这正是题目描述的要求“计数继续从下一个人开始”。上述线性扫描方法中每次淘汰后继续扫描下一个位置自然实现了这一规则。步骤四输出结果遍历person\textit{person}person数组输出所有非零元素即未被淘汰的人即为幸运位置。注意输出格式每个数据的结果前有一行Selection #A结果后有一个空行。复杂度分析时间复杂度每淘汰一个人最多扫描NNN个位置最坏淘汰N−XN-XN−X个人故总时间复杂度O(N×(N−X))O(N \times (N - X))O(N×(N−X))即O(N2)O(N^2)O(N2)N≤50N \le 50N≤50时完全可接受。空间复杂度O(N)O(N)O(N)。代码实现// M*A*S*H// UVa ID: 402// Verdict: Accepted// Submission Date: 2016-07-18// UVa Run Time: 0.050s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intcases0,n,x;string line;while(getline(cin,line)){istringstreamiss(line);issnx;queueintcards;intnumber;while(issnumber)cards.push(number);vectorintperson(n);iota(person.begin(),person.end(),1);intremainingn;while(remainingxcards.empty()false){inttokencards.front();cards.pop();intcurrent0,counter0;while(currentn){if(person[current]0)counter;if(countertoken){person[current]0;remaining--;if(remainingx)gotoskip;counter0;}current;}}skip:coutSelection #cases\n;boolfirsttrue;for(inti0;iperson.size();i){if(person[i]0)continue;if(first)firstfalse;elsecout ;coutperson[i];}cout\n\n;}return0;}总结本题是一道经典的约瑟夫问题变种主要考察以下知识点循环淘汰的模拟需要正确处理“从当前位置继续”和“淘汰后重置计数”的规则。数组标记淘汰使用000标记淘汰比实际删除元素更简单避免频繁调整数组结构。多组数据输入处理使用getline\texttt{getline}getline配合istringstream\texttt{istringstream}istringstream读取不定长整数序列。提前终止条件当剩余人数达到XXX时应立即停止淘汰即使牌堆中还有剩余牌也不再使用。本题的易错点在于淘汰后计数从000重置而不是从111。判断是否已淘汰到XXX人的时机在淘汰一人后立即检查如果remainingX\textit{remaining} XremainingX则跳出循环。当202020张牌用完后无论剩余多少人所有剩余的人都是幸运的。本题虽然模拟过程简单但需要仔细理解题目描述中“从下一个人继续”的细节。通过数组标记法可以有效避免链表操作带来的复杂度同时保证逻辑清晰。