解题思路

这是经典的约瑟夫问题变体。

关键点：

1. 初始时所有同学都有卡片（未被选出）
2. 每次从当前位置开始数 x 个人（x 是上一轮喊出的数字）
3. 如果数到的同学已经没卡片，继续往下数，直到找到有卡片的同学
4. 该同学完成拼图，下一轮从他的下一位开始

模拟过程：

• 使用数组标记每个同学是否还有卡片
• 当前数字 cur = 1（第一个人喊1）
• 当前位置 pos = 1（第一个人开始）
• 当剩余人数 > 1 时循环：
  • 从 pos 开始数 cur 个人
  • 如果数到的位置已经没有卡片，需要继续往下找有卡片的
  • 选出该同学，标记为无卡片
  • cur = 该轮数过的总数 + 1
  • pos = 选中的位置

由于 n < 100，可以直接模拟。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    vector<bool> hasCard(n + 1, true);
    int remaining = n;
    int cur = 1;
    int pos = 1;
    
    while (remaining > 1) {
        int count = 0;
        int idx = pos;
        
        while (count < cur) {
            idx = idx % n + 1;
            if (hasCard[idx]) {
                count++;
            }
        }
        
        while (!hasCard[idx]) {
            idx = idx % n + 1;
        }
        
        hasCard[idx] = false;
        remaining--;
        
        cur = cur + 1;
        pos = idx;
    }
    
    for (int i = 1; i <= n; i++) {
        if (hasCard[i]) {
            cout << i << endl;
            break;
        }
    }
    
    return 0;
}

复杂度分析

• 时间复杂度：O(n²) - 最坏情况每次需要遍历
• 空间复杂度：O(n)