题目描述
E卷 100分题型
100个人围成一圈，每个人有一个编码，编号从1开始到100。
他们从1开始依次报数，报到为M的人自动退出圈圈，然后下一个人接着从1开始报数，直到剩余的人数小于M。
请问最后剩余的人在原先的编号为多少？
输入描述
输入一个整数参数 M
输出描述
如果输入参数M小于等于1或者大于等于100，输出“ERROR!”；
否则按照原先的编号从小到大的顺序，以英文逗号分割输出编号字符串
示例1
输入
3
输出
58,91
示例2
输入
4
输出
34,45,97
题解
这是一个经典的约瑟夫环的问题。
- 使用list结构(双向链表容器)移除中间元素（移除元素复杂度为O(1)）将问题 转换为移除指定位置的元素。
- pos记录最新一轮报数为1的位于lst容器的下表位置。
- 下一轮要移除元素的下标 next = (pos + m) % lst.size()
#include<iostream>
#include <list>
using namespace std;int main() {int m ;cin >> m;// 数据合法性判断if (m <= 1 || m >= 100) {cout << "ERROR!";return 0;}list<int> lst;for (int i = 1; i <= 100; ++i) {lst.push_back(i);}// 当前轮报数为1的下标int pos = 0;while (lst.size() >= m) {pos = (pos + m - 1) % lst.size();// 移除指定位置的元素// 移除一个元素之后pos是不需要动的。[1,2,3,4], pos =2,移除3,[1,2,4],pos会自动指向4了std::list<int>::iterator it = lst.begin();std::advance(it, pos); lst.erase(it);}// 遍历列表for (auto it = lst.begin(); it != lst.end(); ++it) {// 输出元素cout << *it;// 判断是否是最后一个元素if (next(it) != lst.end()) {cout << ","; // 不是最后一个元素，输出逗号}}return 0;
}
