题目描述 有 n n​ 个小朋友围成一圈，玩数数游戏。小朋友们按顺时针顺序，依次编号为 1 ∼ n 1∼n。 初始时， 1 1 号小朋友被指定为领头人。游戏一共会行进 k k​ 轮。在第 i i 轮中，领头人会从他的顺时针方向的下一个人开始，按顺时针顺序数 a i a i ​ 个人。其中，最后一个被领头人数到的人被淘汰出局，这也意味着该轮游戏结束。出局者的顺时针方向的下一个人被指定为新领头人，引领新一轮游戏。 例如，假设当游戏即将开始第 i i 轮时，还剩下 5 5 个小朋友，编号按顺时针顺序依次为 8 , 10 , 13 , 14 , 16 8,10,13,14,16，并且当前领头人为 13 13 号小朋友， a i = 12 a i ​ =12，则第 i i 轮游戏结束后，最后一个被数到的小朋友为 16 16 号小朋友，他将被淘汰出局，并且处于其下一位的第 8 8 号小朋友将被指定为新领头人。 现在，请你求出每一轮次被淘汰的小朋友的编号。 输入描述 第一行两个整数 n , k n,k； 第二行 k k 个整数 a 1 , a 2 , … , a k a 1 ​ ,a 2 ​ ,…,a k ​ 。 输出描述 一行 k k 个整数，其中第 i i 个整数表示在第 i i 轮中被淘汰的小朋友编号。 样例1 输入 7 5 10 4 11 4 1 输出 4 2 5 6 1 样例2 输入 3 2 2 5 输出 3 2 样例3 输入 5 3 10000 10000 1000000 输出 1 2 4 提示 对于 100 % 100% 的数据： 1 ≤ n ≤ 100 1≤n≤100， 1 ≤ k ≤ n − 1 1≤k≤n−1， 1 ≤ a i ≤ 1 0 9 1≤a i ​ ≤10 9 c++

<think>嗯，我现在得仔细看看这个问题。题目是说，有n个小朋友围成一个圈，玩数数游戏。每一轮领头人从顺时针下一个开始数ai个人，最后一个被数到的淘汰。然后下一个人成为新的领头人。我要找出每一轮被淘汰的人的编号。 首先，我得理解这个过程。比如样例1中的输入是7个小朋友，5轮。每一轮的a分别是10,4,11,4,1。输出是4 2 5 6 1。我需要模拟每一轮的情况。 那问题的关键在于如何高效地找到每一轮被淘汰的人。因为如果直接模拟的话，当ai很大时，比如1e9，这时候直接数数会超时，必须找到数学方法来计算位置。 比如，每轮当前剩下m个人，那么领头人要数ai个人，但实际有效次数应该是ai mod m，因为每m次就会循环一圈。不过，可能要考虑起始位置的问题。例如，领头人当前的位置是某个位置，开始数的下一个是顺时针方向的下一个人，然后数ai次。这里需要注意，数的时候，是包括开始的那个人的下一个吗？ 比如样例中的例子，领头人是13，然后数12次。剩下的5个人是8,10,13,14,16。领头人的顺时针下一个人是14。那么数12次的话，从14开始。数12次，每数一次选下一个人。那具体怎么算？ 比如当前有5个人，那么数12次的话，相当于12步。因为每步走一个。所以12 mod 5是2。所以相当于走两步。从14开始，数第12次的话，应该是14（第一个是14，第二个是16，第三个是8，第四是10，第五是13，然后循环。但这里可能需要再仔细想。 或者，领头人开始的位置是当前的位置，然后要开始数的起点是领头人的下一个人。比如，当前领头人是13，那么下一轮的开始位置是14。然后数ai次，每次移动到下一个。那么最后一个被数到的是谁？ 比如，假设当前有m个孩子，领头人的位置是current_leader。那么新的起始点是current_leader的下一个。然后数ai次，每次移动顺时针方向一个，所以总共有ai次移动。那么最终的位置是起始点移动ai-1次后的位置？或者怎么算？ 比如，假设当前圈是A -> B -> C -> D，领头人是A。那么下一轮开始的位置是B。假设ai是3，那么数3次的话，第一个是B，第二个是C，第三个是D。所以被淘汰的是D。这时候，新的领头人是A吗？或者领头人变成D的下一个，即A？ 哦，题目中说，出局者的顺时针方向的下一个人成为新领头人。所以当D被淘汰后，D的下一个是A，所以新的领头人是A？ 那么，如何建模这个过程呢？每次需要维护当前剩余的小朋友的顺序，以及当前的领头人。然后每一轮，根据领头人的位置，找到起始点（即领头人的下一个），然后计算需要移动多少步才能找到被淘汰的人。 关键问题在于，如何高效计算被淘汰的位置。因为当ai很大时，无法一步步模拟，所以必须用数学公式。 比如，当前圈中有m个元素，起始点是s（即领头人的下一个），需要数ai次，那么被淘汰的位置是s开始后的第ai-1个元素？或者第ai个元素？ 比如，当起始点是s，数ai次的话，每一个数对应一个位置。例如，第一次数到s，第二次数到s的下一个，依此类推。这样，数ai次的话，最后的位置是 (s + ai -1) mod m？ 或者，可能更准确的是，起始位置是s，然后要移动ai次，每次移动到顺时针的下一个人。那么总共有ai步移动。最终的位置是 (s + ai -1) % m。这里的m是当前的人数。比如，起始位置是s，移动ai-1次后的位置就是最终被淘汰的位置？ 例如，样例中的例子，当有5个人，起始位置是14，ai是12。那么12 mod5是2。所以起始位置是14，移动11次（因为ai是12次，起始位置是第一个，然后每移动一次是第二个）。所以14的位置在数组中的索引可能要考虑。或者，需要将圈中的当前顺序保存为一个列表，每次维护这个列表的顺序，以及当前领头人的位置。 假设我们维护一个双向链表或者数组，这样可以快速找到下一个元素。但这样的话，当n很大时，每次删除元素需要O(m)的时间，而总共有k轮，总时间是O(kn)，对于n=100，k=100来说，应该没问题。 但问题在于，如何处理ai非常大的情况。比如，当ai是1e9，这时候必须找到模运算的方法，而不实际遍历。 因此，关键点在于，每一轮当前剩余的人数m（初始是n，每轮减一），当前领头人位置，那么该轮被淘汰的人的位置可以通过计算得出。 举个例子，假设当前圈有m个孩子，领头人是L。下一轮的起始点是L的下一个孩子S。然后数ai次，即从S开始数ai个孩子。那被淘汰的是S的第ai-1个顺时针移动后的位置吗？ 例如，起始点是S，数1次的话，就是S自己。数2次的话，是S的下一个。以此类推。所以，总共有ai次，所以移动ai次后的位置是（S的索引 + ai -1） mod m？ 或者，可能需要更仔细地分析。例如，当前的圈顺序是顺时针排列的，比如当前圈的顺序是 [A,B,C,D]，当前领头人是D，那么下一轮的起始点就是A。数ai次的话，比如ai=3，那么数到的是A、B、C。被淘汰的是C。此时，新的领头人是D吗？或者，被淘汰的是C，所以他的下一个是D，所以新领头人就是D？ 这可能需要看题目的例子。例如，样例中的例子，当被淘汰的是16号，那么他的下一位是8号，成为新的领头人。原来的顺序是8、10、13、14、16，领头人是13。所以下一轮的起始点是14，数12次，得到的是16。然后新领头人是16的下一个，即8号。 所以，在每一轮中，被淘汰的位置是起始点（领头人的下一个）开始数ai次后的位置。那么，如何计算这个位置？ 假设当前圈有m个元素，起始位置是s，那么数ai次后的位置是（s + ai -1） mod m。因为，例如，起始位置是s，数1次就是s。数2次的话，s和s+1。所以，总次数是ai，那么移动ai-1次后的位置就是被淘汰的位置。 这样，被淘汰的位置是 (s + ai -1) mod m。这里的s是起始位置（领头人的下一个）在圈中的索引。 但这里的问题是如何维护圈中的顺序，以及如何找到s的索引。 可能的解决方案是，维护一个动态的数组或列表，表示当前的圈中的孩子的顺序。然后，当前领头人的位置在数组中的某个索引。每轮，起始点s是领头人的下一个索引。例如，如果当前领头人在索引i，那么s是(i+1) % m，其中m是当前圈的大小。然后，计算被淘汰的位置的索引是 (s + ai -1) % m。然后，删除该索引处的元素，新的领头人变为被淘汰者的下一个索引，即 (淘汰的索引 + 1) % (m-1)？或者需要看具体情况？ 或者，更准确地说，当被淘汰的是索引p，那么新的领头人应该是数组中被淘汰元素的下一个元素。例如，如果当前数组是 [8,10,13,14,16]，领头人在索引2（即13）。起始点s是索引3（14）。数ai=12次，得到被淘汰的位置是 (3 + 12-1) mod5=14 mod5=14%5=4。索引4对应的元素是16。删除后，数组变成[8,10,13,14]，新的领头人是16的下一个，即数组中的索引0（8），因为原来的数组在删除索引4后，原来的索引0是8，所以新的领头人是8。 因此，关键点在于如何维护这个动态变化的数组，以及每个元素的索引，同时正确计算每一步的起始点s和被淘汰的位置。 所以，算法的大致思路是： 1. 初始化一个列表，存储当前圈中的孩子的编号，顺序是顺时针方向。初始时，顺序是1到n，但可能需要验证。例如，初始时领头人是1号，那么列表的顺序应该是按顺时针排列的。比如，初始时，圈的顺序是1,2,3,...,n，顺时针排列。领头人是第一个元素（索引0）。 2. 维护当前领头人在列表中的索引current_leader_idx。初始时为0（因为初始时领头人是1号，假设列表的顺序是1,2,3,...,n）。 3. 对于每一轮i，从1到k： a. 当前列表的大小是m = n - (i-1)。因为每轮淘汰一人，初始n，第i轮时已经淘汰i-1人。 b. 当前起始点s的索引是 (current_leader_idx +1) % m。因为领头人的下一个是起始点。 c. 计算ai的有效步数：step = ai % m。如果step为0的话，相当于ai是m的倍数，那么模后是0，但此时相当于走m步，即回到起始点。可能需要处理这种情况。例如，当ai=5，m=5，那么step=0。这时候，实际应该取m。 所以，可能需要将step设置为 (ai-1) % m +1？或者，计算有效步数时，应该使得总步数等于ai mod m，但ai可能是0的情况如何处理？ 或者，正确的计算应该是：被淘汰的位置是 (s + ai -1) % m。例如，当ai是12，m是5，那么s是3（索引），12-1=11，3+11=14 mod5=4。对应例子中的情况，正确。 所以，不管ai的大小如何，直接计算（s + ai-1）%m即可。因为当ai是0的话，这可能不适用，但题目中的输入条件中，ai>=1。所以不需要考虑ai为0的情况。 所以，被淘汰的索引是：eliminated_idx = (s + ai -1) % m. 但是，当ai mod m等于0时，比如ai是5，m是5，那么（s +5-1）%5= (s+4) mod5。假设s是0的话，那么4 mod5=4，即第五个元素。这可能需要看是否正确。 例如，当s是0，ai是5，m=5。则被淘汰的位置是（0+5-1）%5=4%5=4，即第五个元素。而数5次的话，从s开始，依次是0,1,2,3,4，共5次。所以正确。 所以，这个公式是正确的。 4. 被淘汰的索引是eliminated_idx。然后，这个索引对应的元素被删除，成为答案的一部分。 5. 新的领头人的索引是 (eliminated_idx) % (m-1) 的下一个？或者，原来的数组中，被删除的索引之后的元素，他们的索引会自动调整。例如，假设原来的数组是 [A,B,C,D,E]，索引0-4。假设被删除的是索引3（D），那么数组变成[A,B,C,E]，原来的E的索引变成3。此时，被删除的元素的下一个元素的索引是（3+1）%5=4，但是数组变小后，所以新的数组的长度是4。那么新的领头人的索引是（3+1）%4=0？或者可能需要重新计算。 根据题目中的例子，当被删除的是索引4（元素16），原来的数组变成[8,10,13,14]。新的领头人应该是16的下一个，即8。在原来的数组中，被删除的索引是4，那么他的下一个是索引0（因为是环形的），所以新的领头人的索引在删除后的数组中应该是0？或者，在删除后的数组中，原来的索引0是8，原来的索引1是10，等等。所以，新的领头人应该是原来的数组中被删除元素的下一个元素的索引。例如，原来的数组中被删除的是索引p，那么他的下一个元素的索引是（p+1）%m。但在删除之后，数组长度变为m-1，那么新数组中的领头人的索引是 (p+1) %m 对应的新数组的位置？ 或者，更简单地说，在原来的数组中，被删除的元素的索引是p。那么，在删除之后，数组中的元素会被调整为： 例如，原数组是 [0,1,2,3,4]（索引0~4），删除p=2。则新数组是 [0,1,3,4]。此时，原来的索引3的元素现在位于新数组的索引2的位置。原来的索引4的元素现在位于索引3的位置。 因此，被删除元素的下一个元素在原数组中的索引是 (p+1) %m。比如，当m=5，p=4时，(4+1) mod5=0。原数组中索引0的元素是8。那么，在删除之后，新数组的长度是4，原来的索引0的元素在新数组中的索引是0。所以，新的领头人的索引是0。 因此，新的领头人的索引对应于原数组中(p+1) %m的位置，但在新数组中的索引需要重新计算吗？ 例如，原数组是 [A,B,C,D,E]，索引0~4。删除p=4的元素E，得到新数组[A,B,C,D]。原来的下一个索引是0，所以新领头人的索引是0。 因此，新的领头人就是原数组中(p+1) %m的位置对应的元素。而该元素在新数组中的索引可能需要根据原数组中的位置来确定。例如，如果原数组中的元素顺序不变，删除p后的数组中，所有在p之后的元素向前移动一位。所以，原数组中索引大于p的元素在新数组中的索引是原索引-1，而索引小于p的元素保持不变。因此，原数组中(p+1) %m的位置，如果该位置大于p，那么在新数组中的索引是原位置-1。否则，保持原位置。 这似乎比较复杂。有没有更简单的方法？ 或许，维护当前数组中的元素顺序，以及当前领头人的索引。每次删除一个元素后，新的领头人的索引就是原数组中(p+1) %m的位置，然后在新数组中的索引是该位置对应的元素是否被删除？ 或者，当删除元素p后，新的数组的长度是m-1。新的领头人的索引是原数组中(p+1) %m的位置在新数组中的索引。例如，原数组的索引是0~4，p=4。那么 (p+1)%5=0。新数组的长度是4，原索引0的元素在新数组中还是0。所以新的领头人索引是0。 另一个例子：原数组索引是0~4，p=3。那么(p+1) mod5=4。原数组中的索引4的元素在新数组中的索引是3（因为删除了索引3的元素，后面的元素前移）。所以，新的领头人的索引是3。 因此，新的领头人的索引等于原数组中的(p+1) mod m的位置，如果该位置大于p的话，那么在新数组中该位置的索引是原位置-1。否则，是原位置。 这似乎很复杂，但可能有一种方式可以直接计算新的领头人的索引： 新的领头人索引等于 (p+1) %m。但是，这个索引可能已经被删除了吗？ 不，因为p是被删除的索引，而新的数组长度是m-1，所以原来的索引只能在0到m-1之间。原数组中，当p被删除后，新的数组的索引是0到m-2。那么，原数组中的索引为q的元素，如果q <p，则在新数组中的索引还是q。如果 q>p，则在新数组中的索引是 q-1。 所以，原数组中的索引q的元素，在新数组中的索引为：如果 q <p → q；否则 q-1. 那么，原数组中(p+1) mod m的位置是新的领头人的元素，该元素在新数组中的索引为： q = (p+1) %m. 如果 q <p → 新索引是 q. 如果 q >p → 新索引是 q-1. 但是，由于p的取值范围是0 ≤ p <m，而 q = (p+1) modm。当 p+1 <m → q=p+1. 否则，q=0. 所以，当 q <p的情况只能是当 q=0，而 p =m-1。例如，当 p=4（m=5），那么 q=0。此时，在新数组中，原索引0对应的元素在新数组中的索引是0。所以新的领头人的索引是0. 当 q >p的情况，例如，p=2，m=5 → q=3>2。此时，在新数组中，原索引3对应的元素的索引是3-1=2（因为 p=2被删除，所以原索引3在m=5时，在新数组中变成2）。所以，新的领头人索引是 q-1 =3-1=2. 所以，新的领头人的索引的计算方式为： new_leader_idx_in_new_array = q >p ? q-1 : q. 但是，当 q=0时（例如，p=m-1的情况），那么 q=0 <p，所以 new_leader_idx_in_new_array=0. 这样，新的领头人的索引就可以计算出来。 因此，总结每一轮的处理步骤： 1. 当前数组是current_list，长度是m. 2. 当前领头人的索引是current_leader_idx. 3. 起始点s的索引是 (current_leader_idx +1) %m. 4. 计算被淘汰的索引：eliminated_idx = (s + ai -1) %m. 5. 被淘汰的元素是current_list[eliminated_idx]. 6. 计算新的领头人在原数组中的索引：q = (eliminated_idx +1) %m. 7. 现在，从current_list中删除eliminated_idx的元素，得到新的数组new_list，长度为m-1. 8. 新的领头人的索引在new_list中是： if q > eliminated_idx → q-1 else → q 但需要注意，如果 q == m（比如，当eliminated_idx是m-1，那么 q=0）。 例如，当q=0，而eliminated_idx= m-1（假设m=5，则 q=0，而 eliminated_idx=4。此时，q <eliminated_idx？ 是的。所以，新的索引是q=0。而原q=0在新数组中对应的元素是原来的0号元素，未被删除，所以正确。 所以，在删除元素后，新的领头人的索引是： new_leader_idx = q > eliminated_idx ? q -1 : q; 其中，q = (eliminated_idx +1) %m. 现在，如何用代码实现这个过程？ 例如，可以用一个vector或list来维护当前的children的顺序。每次执行删除操作，并记录新的领头人的位置。 但使用vector的话，删除元素需要O(m)的时间，对于m=100，k=100次，总时间是1e4，应该没问题。但是当m很大时，比如1e5，这可能不行。但题目中的n<=100，所以完全没问题。 因此，代码的大致思路如下： - 初始化current_list为1到n的数组。 - current_leader_idx初始为0. - 对于每个a_i： - m = current_list.size(); - s = (current_leader_idx +1) %m; - eliminated_idx = (s + a_i -1) %m; - 记录current_list[eliminated_idx]到结果中。 - q = (eliminated_idx +1) %m; - 删除current_list中的eliminated_idx位置的元素. - 计算新的current_leader_idx: 如果 q > eliminated_idx → new_leader_idx = q-1; else → new_leader_idx = q; 但是，当删除元素后，数组的大小变为m-1。而q的可能取值范围是0到m-1。例如，如果 eliminated_idx是2，m=5，那么 q可以是3。在删除后，原数组中的3号位置元素现在的索引是2。所以，当 q>eliminated_idx时，新的索引是q-1，否则是q. 这样，就可以维护current_leader_idx的正确位置。 现在，考虑样例1的输入： 输入： 7 5 10 4 11 4 1 输出：4 2 5 6 1 初始current_list是[1,2,3,4,5,6,7] current_leader_idx=0. 第一轮a_i=10. m=7. s = (0+1)%7=1. eliminated_idx=(1+10-1) mod7=10 mod7=3 → current_list[3]=4. 所以输出第一个元素4. q=(3+1) mod7=4. 删除索引3的元素，current_list变成[1,2,3,5,6,7]. 现在，q=4，而原来的m=7，所以q=4>3（被删除的索引3），所以 new_leader_idx=4-1=3. 但是 current_list的长度现在是6，所以3是有效的索引吗？ current_list删除索引3的元素后，新数组的索引是0~5。原q=4对应的元素是原数组中的5（索引4），在删除后，原数组中的索引4的元素（6）现在位于新数组中的索引3。所以，此时新的current_leader_idx是3。即，新数组中的索引3对应元素6。 所以，下一轮的current_leader_idx是3. 第二轮a_i=4. m=6. s=(3+1)%6=4. eliminated_idx=(4+4-1) mod6=7 mod6=1. current_list是[1,2,3,5,6,7]. 索引1处的元素是2。所以输出第二个元素2. q=(1+1) mod6=2. 删除索引1的元素，current_list变成[1,3,5,6,7]. q=2，原m=6。被删除的索引是1。q=2>1，所以 new_leader_idx=2-1=1. 现在，current_list的长度是5，所以new_leader_idx=1对应的元素是3. 第三轮a_i=11. m=5. s=(1+1)%5=2. eliminated_idx=(2 +11-1) mod5=12 mod5=2 → current_list[2]=5. 输出第三个元素5. q=(2+1) mod5=3. 删除索引2的元素，current_list变成[1,3,6,7]. q=3>2 → new_leader_idx=3-1=2. 此时current_list是[1,3,6,7]，new_leader_idx=2对应的元素6. 第四轮a_i=4. m=4. s=(2+1)%4=3. eliminated_idx=(3 +4-1) mod4=6 mod4=2. current_list是[1,3,6,7]. 索引2的元素是6. 输出第四个元素6. q=(2+1) mod4=3. 删除索引2的元素，current_list变成[1,3,7]. q=3>2 → new_leader_idx=3-1=2. 但是 current_list现在长度是3。所以索引2是有效的。此时current_leader_idx=2对应的元素7. 第五轮a_i=1. m=3. s=(2+1)%3=0. eliminated_idx=(0 +1-1) mod3=0 mod3=0 → current_list[0]=1. 输出第五个元素1. 所以最终输出是4 2 5 6 1，与样例一致。 这样，算法是正确的。 现在，需要将这个逻辑用代码实现。用C++的话，可以用vector来维护current_list，每次删除元素，并更新current_leader_idx。 需要注意的是，当删除元素后，新的数组的索引的计算方式。例如，在删除一个元素后，原数组中比该索引大的元素的索引会减一。 因此，代码的大致步骤： - 读取n和k，以及数组a. - 初始化current_list为1~n的vector. - current_leader_idx=0. - 对于每个a_i: - m = current_list.size(); - s = (current_leader_idx +1) %m; - eliminated_idx = (s + a_i -1) %m; - 输出current_list[eliminated_idx]. - q = (eliminated_idx +1) %m; - current_list.erase(current_list.begin() + eliminated_idx); - 计算新的current_leader_idx: if (q > eliminated_idx) { new_leader_idx = q -1; } else { new_leader_idx = q; } 但是，q的可能范围是0到m-1，而删除后的数组长度是m-1. 例如，当原m=5，q=4，而eliminated_idx=3。那么 q>eliminated_idx → new_leader_idx=4-1=3。删除后的数组长度是4，所以3是有效索引。 - current_leader_idx = new_leader_idx. 这样，就能正确维护current_leader_idx的索引。 现在，测试样例2： 输入： 3 2 2 5 输出：3 2 初始current_list=[1,2,3], current_leader_idx=0. 第一轮a=2. m=3. s=(0+1)%3=1. eliminated_idx=(1+2-1)=2 mod3=2 →元素3被淘汰。输出3. q=(2+1) mod3=0. 删除后数组是[1,2]. new_leader_idx的判断：q=0，被删除的索引是2。所以q <2吗？是的，所以 new_leader_idx=0. 现在current_leader_idx=0. 第二轮a=5. m=2. s=(0+1)%2=1. eliminated_idx=(1+5-1)=5 mod2=1 →元素2被淘汰。输出2. 所以输出是3 2，与样例一致。 另一个样例3： 输入： 5 3 10000 10000 1000000 输出：1 2 4. 初始current_list=[1,2,3,4,5], current_leader_idx=0. 第一轮a=10000. m=5. s=1. eliminated_idx = (1+10000-1) mod5=10000 mod5=0 →current_list[0]=1被淘汰。输出1. q=(0+1) mod5=1. 删除后数组是[2,3,4,5]. new_leader_idx: q=1，被删除的索引是0。因为1>0 →new_leader_idx=1-1=0. 此时，current_leader_idx=0，数组是[2,3,4,5]. 第二轮a=10000. m=4. s=(0+1)%4=1. eliminated_idx=(1+10000-1) mod4=10000 mod4=0 → current_list[0]=2被淘汰.输出2. q=(0+1) mod4=1. 删除后的数组是[3,4,5]. new_leader_idx: q=1>0 →1-1=0. current_leader_idx=0. 第三轮a=1000000. m=3. s=(0+1)%3=1. eliminated_idx=(1+1000000-1) mod3=1000000 mod3=1 → current_list[1]=4被淘汰.输出4. 所以最终输出1 2 4，正确。 所以，算法是正确的。 现在，如何用C++实现？ 需要注意，vector的erase操作会改变后续元素的索引。例如，当删除索引i，那么原索引i+1的元素现在位于索引i的位置，依此类推。 但按照前面的逻辑，当计算new_leader_idx时，已经考虑了这一点。例如，当q是原数组中的索引，而q>被删除的索引i，那么新索引是q-1。否则是q。这正好对应vector删除元素后的索引变化。 因此，代码的大致结构如下： #include <iostream> #include <vector> using namespace std; int main() { int n, k; cin >> n >>k; vector<int> a(k); for (int i=0; i<k; ++i) { cin >>a[i]; } vector<int> current(n); for (int i=0; i<n; ++i) { current[i] = i+1; } int current_leader = 0; // 初始领头人索引是0 vector<int> res; for (int ai : a) { int m = current.size(); int s = (current_leader +1) %m; int eliminated_idx = (s + ai -1) %m; res.push_back(current[eliminated_idx]); int q = (eliminated_idx +1) %m; current.erase(current.begin() + eliminated_idx); if (q > eliminated_idx) { current_leader = q-1; } else { current_leader = q; } // 当删除后，current的大小是m-1. // current_leader应该在0..m-2范围内. // 例如，当m=5时，删除后是4元素，current_leader应在0~3. // 而根据计算，q的取值范围是0~4，当 q>eliminated_idx时，q-1可能等于4-1=3，正确. } for (int x : res) { cout << x << " "; } cout << endl; return 0; } 测试样例1： 输入7 5 10 4 11 4 1 输出4 2 5 6 1 →正确。 测试样例3： 输入5 3 10000 10000 1000000 →输出1 2 4. 第一轮： ai=10000, m=5. s=1. eliminated_idx= (1+10000-1) mod5=10000 mod5=0 →current[0]=1. q=(0+1) mod5=1. 因为q=1>0 → current_leader=0. 数组变成[2,3,4,5]. 第二轮ai=10000. m=4. s=0+1=1 mod4=1. eliminated_idx=(1 +10000-1) mod4=10000 mod4=0 → current[0]=2. q=(0+1) mod4=1. 因为q=1>0 → current_leader=0. 数组变成[3,4,5]. 第三轮ai=1e6. m=3. s=0+1=1 mod3=1. eliminated_idx=(1 +1e6-1) mod3=1e6 mod3=1 →current[1]=4. 输出正确。 因此，代码是正确的。</think>要解决这个问题，我们需要模拟一个数数游戏的过程，其中每一轮根据给定的规则确定被淘汰的小朋友，并更新领头人。关键在于高效计算每一轮被淘汰的位置，避免因数值过大导致的超时问题。 ### 方法思路 1. **初始设置**：将小朋友按顺时针顺序编号，初始领头人为1号。 2. **轮次处理**：对于每一轮，从当前领头人的下一位开始数数，计算被淘汰的位置。 3. **模运算优化**：由于数数次数可能极大，使用模运算简化计算。 4. **动态维护**：每轮结束后，更新剩余小朋友的列表和新的领头人位置。 ### 解决代码 ```cpp #include <iostream> #include <vector> using namespace std; int main() { int n, k; cin >> n >> k; vector<int> a(k); for (int i = 0; i < k; ++i) { cin >> a[i]; } vector<int> current; for (int i = 1; i <= n; ++i) { current.push_back(i); } int current_leader = 0; // 当前领头人的索引 vector<int> result; for (int ai : a) { int m = current.size(); int s = (current_leader + 1) % m; int eliminated_idx = (s + ai - 1) % m; // 记录被淘汰的编号 result.push_back(current[eliminated_idx]); // 计算新领头人的原始位置 int q = (eliminated_idx + 1) % m; // 删除被淘汰的元素 current.erase(current.begin() + eliminated_idx); // 更新领头人索引 if (q > eliminated_idx) { current_leader = q - 1; } else { current_leader = q; } } for (int num : result) { cout << num << " "; } cout << endl; return 0; } ``` ### 代码解释 1. **输入处理**：读取小朋友数量 `n` 和轮次 `k`，以及每轮的次数数组 `a`。 2. **初始列表**：创建初始小朋友列表 `current`，按顺时针顺序排列。 3. **轮次模拟**： - 计算当前轮次的起始位置 `s`，即领头人的下一位。 - 使用模运算确定被淘汰的位置 `eliminated_idx`。 - 记录被淘汰的小朋友编号，并从列表中移除。 - 根据规则更新新的领头人位置。 4. **输出结果**：输出每一轮被淘汰的小朋友编号。 该方法通过动态维护小朋友列表和领头人位置，结合模运算高效处理大数数次数，确保在合理时间内完成所有轮次的计算。