题目分析

这是一个基于约瑟夫环问题变种的模拟题。题目描述了一个抽签场景：士兵们站成一排，按特定规则淘汰，最终剩下的人可以回家。关键规则如下：

1. 初始条件：有N个士兵（位置1到N）和20张卡片
2. 淘汰规则：
   • 从第一张卡片开始，按当前卡片的值K淘汰士兵
   • 每次数到第K个人时将其淘汰，然后从下一个人重新开始计数
   • 当数完一轮（遍历完当前所有幸存者）后，使用下一张卡片继续淘汰过程
3. 终止条件：当剩下X个人时停止淘汰，这些人即为幸运者

算法思路

1. 数据结构：使用布尔数组position标记每个位置的士兵是否被淘汰
2. 模拟过程：
   • 逐张使用卡片，每张卡片使用一轮
   • 在每一轮中，遍历所有位置，对未被淘汰的士兵计数
   • 当计数达到当前卡片值时，淘汰该士兵并重置计数器
3. 终止判断：当幸存者数量等于X时停止模拟

解决代码分析

#include <iostream>
#include <cstdio>
#include<bits/stdc++.h> 
using namespace std;
 
const int maxn = 55;
int cards[25];
bool position[maxn];
 
int main(){
    int participants,lucky;
 
    int counter = 1;
    while(scanf("%d%d",&participants,&lucky)!=EOF){
        int i,j;
        for(i = 0 ; i < 20 ; ++i){
            scanf("%d",&cards[i]);
        }
 
        int left_num = participants;
        memset(position,1,sizeof(position));
 
        for(i = 0 ; left_num > lucky ; ++i){//在left_num>lucky的情况下,不断的扫卡片数组
            int k = 0;//标记数了多少个人
            for(j = 0 ; (j <participants) && left_num > lucky ; ++j ){//扫position[]数组
                if(position[j]){//如果这一个人还在队列里面
                    if(++k == cards[i]){//如果数到了卡片中要求的数字
                        --left_num;//幸存者的人数-1
                        k=0;
                        position[j] = false;//那个人出队
                    }
                }
            }
        }
 
        if(counter != 1){
            printf("\n");
        }
        printf("Selection #%d\n",counter++);
        for(i = 0 ; i < participants ; ++i){
            if(position[i]){
                printf("%d ",i+1);
            }
        }
        printf("\n");
    }
 
    return 0;
}

代码解释

1. 输入处理：

   • 使用scanf读取多组测试数据
   • 每组数据包含N（人数）、X（幸运人数）和20张卡片的值

2. 初始化：

   • position数组初始化为全1，表示所有人都在队列中
   • left_num初始化为N，表示初始幸存者数量

3. 模拟淘汰过程：

   • 外层循环：使用卡片，直到剩下X个人
   • 内层循环：遍历所有位置，对未被淘汰的士兵计数
   • 当计数达到当前卡片值时，淘汰该士兵并重置计数器

4. 输出结果：

   • 按指定格式输出每组结果
   • 注意每组结果之间有一个空行，最后一组后不需要空行

复杂度分析

• 时间复杂度：O(N×M)，其中N是人数，M是卡片使用次数（通常为20）
• 空间复杂度：O(N)，主要用于存储士兵状态

关键点

1. 卡片循环使用：题目保证在20张卡片内完成淘汰，因此无需担心卡片不足
2. 位置标记：使用布尔数组高效标记士兵状态
3. 计数重置：每次淘汰一人后，计数器需要重置为0
4. 输出格式：注意每组结果之间的空行处理

该算法通过直接模拟淘汰过程，确保了正确性，同时利用数组操作保证了效率，能够在题目限制时间内完成计算。