18063 圈中的游戏

### 思路

这个问题是经典的约瑟夫环问题。我们可以使用链表来模拟这个过程。具体步骤如下：
1. 创建一个循环链表，表示所有人。
2. 从第一个人开始，依次报数。
3. 每报到3的人退出圈子，直到只剩下一个人。

### 伪代码

```
function josephus(n):
    create a circular linked list with n nodes
    current = head of the list

    while more than one node in the list:
        move current to the next node twice (to skip two nodes)
        remove the node after current (the third node)

    return the value of the remaining node
```

### C++代码

#include <iostream>
using namespace std;struct Node {int data;Node* next;Node(int val) : data(val), next(nullptr) {}
};int findLastPerson(int n) {// 创建循环链表Node* head = new Node(1);Node* prev = head;for (int i = 2; i <= n; ++i) {prev->next = new Node(i);prev = prev->next;}prev->next = head; // 形成循环链表// 初始化指针Node* current = head;while (current->next != current) {// 移动两次for (int i = 0; i < 2; ++i) {current = current->next;}// 删除当前节点Node* temp = current->next;current->data = temp->data;current->next = temp->next;delete temp;}int lastPerson = current->data;delete current;return lastPerson;
}int main() {int n;cin >> n;cout << findLastPerson(n) << endl;return 0;
}

### 总结

通过使用循环链表，我们可以有效地模拟报数和删除操作。每次报数到3时，删除相应的节点，直到只剩下一个节点。这个方法的时间复杂度是O(n)，适合处理较大的输入规模。