东华OJ的基础题列表里第41题叫“环”。我第一次看到这个题名的时候还以为是数据结构里的链表成环判断结果点进去才发现题面写的是n个人围成一圈从1号开始报数报到m的人出圈然后从下一个人重新报数反复执行直到剩一个人输出这个人的编号。这不就是经典的约瑟夫环么。用C解这道题既能练到循环模拟又能把递归和递推的思路一起打通而且这道题还经常被拿来当面试算法题的变体值得认真写一写。这篇文章我就照着我在东华OJ上的做题经验把从暴力模拟到数学递推的几种解法、完整可提交代码、容易踩的坑以及相关扩展全部盘一遍。1. 题目到底在考什么从“环”到约瑟夫环1.1 题面核心与输入输出风格先聊聊题面。常见题干是有n个人围成一圈编号从1到n。从第1个人开始从1开始报数报到m的人离开圈子下一个人从1继续报数。问最后留下的人的编号是多少。输入一般是一行两个整数n和m输出一个整数。东华的评测机多组输入是常态所以代码里要写成while (cin n m)这种有些版本会用0 0作为结束标志。这道题的关键在这两个数字的范围。我见过有的版本n最大到1000模拟随便过也有的版本n能到10万甚至百万这时候如果还用链表硬转十有八九会超时。所以基础题不只是让你AC还得琢磨一下复杂度。东华OJ这道“环”在基础题里的位置不算靠后意味着你至少已经会数组、循环、函数这些基础语法了正好可以用它来检验自己对“抽象过程”的理解。1.2 为什么它是“基础题分水岭”我个人觉得东华OJ把它放在基础题里是有点“心机”的。表面上看你只要会while循环和数组就能写但实际上它考察了三个层次的能力第一层是会模拟理解什么叫“循环”比如下标越界取模回绕第二层是会选用合适的数据结构比如循环链表、std::list、vector的删除操作第三层是能发现数学规律直接递推。很多刷题的人第一层就过了但第三层才是这个题真正的闪光点。从编码量来说模拟法的代码大概30到50行递推法几行就写完。差距这么大根源在于你有没有跳出“翻译题面”的惯性。我后来带过几个学弟发现他们最常犯的错就是把题目当成流程说明书一步步照做却从不去想“每次删除后下一轮的人是怎么重新编号的”。一旦开始思考重新编号递推公式自然就出来了。这就是这道题真正的价值所在。2. 三种解法逐层拆解从模拟到数学2.1 循环链表模拟最贴近题面的思路最直观的写法就是真的维护一个环。C里可以用std::list 存1到n然后拿迭代器从头开始走。每走m-1步就删除当前节点输出或者记下来然后从下一个节点继续。这个思路几乎就是题面的翻译适合用来建立直观感觉。需要注意的点std::list不是随机访问容器不能直接下标只能用迭代器。走到end()时要立刻赋值为begin()这样才能真的“转圈”。删除节点后迭代器会失效但erase会返回下一个有效迭代器所以删除后要马上接住这个返回值。我见过很多人写了一个类似it people.erase(it)之后又在else分支里it结果删除时跳过了一个人。这种细节等会儿在坑点章节细聊。链表模拟的复杂度是O(n*m)因为每删除一个人都要走m步一共要删除n-1个人。如果n和m都不大这是最好理解的解法。但千万要记住它只是“直观”不是“优秀”。你以为你在用链表模拟环其实本质上还是在暴力扫描只是把数组换成了链表而已。2.2 数组标记模拟常数小代码更简单不想用链表的话用数组加标记也可以。开一个vector alive(n 1, true)然后循环找“下一个还活着的人”。用一个pos表示当前位置每次报数其实是数过m个存活节点。每次删除就把alive[pos]设为false然后pos继续往下找。这个解法优势是代码直观不容易出现迭代器失效的问题缺点是当m很大时每个m都需要扫描很多已经被删掉的空位最坏情况一样是O(n*m)但常数比链表小。东华OJ基础题的数据量用这个写法通常也能过。不过既然要刷题还是建议一步到位看2.3。我更推荐数组标记法作为“模拟类的标准答案”因为不需要处理链表迭代器出错概率更低。直接写一个do-while循环先从当前位置往下一个方向探索遇到alive为true的人计数计到m就停止。关键是要理解do-while和while的区别当前人已经报过数了所以第一步一定是先移动到下一个人而不是再次判断当前人。很多人在这一步错位导致结果差一。2.3 数学递推O(n)的终极解法约瑟夫环有一个非常优雅的递推公式可以做到O(n)。这里说一个很多人第一次看不懂的推导。我们从最后剩下1个人的时候往前推。假设当前圈子大小为i最后幸存者在“以0为起始编号”的方案里的编号是f(i)。当圈子从i-1扩张到i时我们需要把上一次幸存者的新编号平移m位因为在第i个人加进来之前每次都是数到m删除一个人删除之后所有人会被重新编号。所以递推是f(1) 0f(i) (f(i-1) m) % i, i 2最后f(n)是以0为基准的编号输出f(n)1就是1到n编号下的答案。这个公式为什么是对的可以这么理解当人数从i-1变成i时我们相当于在上一轮幸存者的基础上往“未来”方向平移了m个位置然后对i取模。因为每一步淘汰都会让环的起点发生变化这种起点偏移正好是m。你不需要完全手算推导但至少要记住“幸存者编号在人数扩张时是向后平移m再取模”这个结论。代码就几行背下来容易理解难。实测下来递推法在n100万、m100万时依然飞快因为只有一层循环每次做一次加法和取模。这是真正的O(n)算法面试时写出这个版本绝对比模拟法加分。3. 实操过程与C代码实现3.1 完整可提交代码数组模拟版先给一个比较稳的版本适合绝大多数基础题数据范围。#include iostream #include vector using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; while (cin n m) { vectorbool alive(n 1, true); int cnt n; int idx 1; while (cnt 1) { int step m; while (step--) { do { idx; if (idx n) idx 1; } while (!alive[idx]); } alive[idx] false; cnt--; } for (int i 1; i n; i) { if (alive[i]) { cout i endl; break; } } } return 0; }这个代码的坑在于内层do-while。每次淘汰一个人后idx停在被淘汰的位置下一轮报数要从下一个人开始所以外层的while会先做step m内层先idx再判断alive。这样就能保证报数起点正确。如果直接让idx从1开始会发现结果错一位。我第一次写的时候就栽在这里后来改成do-while才顺过来。还有一个细节这里的step--循环次数是m含义是“移动m次”。因为当前idx本身就是第一个报数的人要从他往后数m步而不是先移动一步再数m-1步。可以自己拿n5, m3试一下第一个人是1号报数1接着2号报数23号报数3所以从1号到3号需要移动2步而不是3步等一下这里的逻辑要仔细我们的do-while是先移动再判断然后计数一次。我们希望最终idx指向报数m的人。当前idx是报数1的人报数2的人需要移动1步报数3的人需要移动2步。所以移动步数是m-1而不是m。那这个代码内层do-while每次都被算作一步移动那应该循环m-1次才对。我们来验证一下。上面代码外层while (step--)执行m次每次内层先idx到下一个存活者然后这一圈算一步。初始idx指向当前报数起点报数1第一次循环移动到报数2的人第二次移动到报数3的人第三次移动到报数4的人这样到第m次移动到报数第m1的人看起来不对。实际上do-while的结构是先移动然后停止条件判断的是alive不是计数。所以整个内层循环完成后idx已经移动了m次指向报数m1的人。但是因为alive[idx]是true停止。所以这个代码会让多移一个人。等等我的代码有问题。让我们重新推导。常见的约瑟夫实现从当前起数到第m个人删除。如果当前在第一个人位置需要走m-1步到第m个人。用do-while写的版本常常是先idx到下一个然后判断重复m-1次还是m次让我们用n5, m3初始idx1都活着。外层第一次删除我们希望最终idx3因为1报12报23报3。如果代码循环m3次内层do-while第一次idx -2alive[2]truedo-while条件!alivefalse退出内层。此时idx2。外层step--后进入相同step不对外层while (step--)是执行一个大循环里面的do-while只执行一次就退出所以step从3减为2然后idx从2开始再次do-whileidx -3退出。step从2减为1然后idx -4退出。step变为0整个外层结束。此时idx4alive[4]false不对最终idx4删除了4号。但正确应删除3号。所以这个代码是错的我需要修正。看来我的草稿有bug在博文里不能提供错误代码。需要重新编写正确数组模拟。我们来规则数组模拟std常见写法int s 0; for (int i 2; i n; i) s (s m) % i;数组模拟删除可以用一个循环指针移动m-1步到报数m的人while (cnt 1) { int step m; while (step-- 1) { // 移动m-1次 do { pos; if (pos n) pos 1; } while (!alive[pos]); } alive[pos] false; cnt--; // 删除后pos停留在被删位置下一轮从下一个人开始所以外层开始前要pos }让我们理清。经典做法是用一个下标cur表示当前报数的人然后移动m-1次到出列的人出列后cur指向出列者的下一个通过cur找到下一个存活然后继续。例如int cur 1; while (cnt 1) { for (int i 1; i m; i) { // 移动m-1步 do { cur; if (cur n) cur 1; } while (!alive[cur]); } alive[cur] false; cnt--; // 现在cur是刚删除的位置下一轮要从cur的下一个开始。 do { cur; if (cur n) cur 1; } while (!alive[cur]); }但要注意如果m1for循环不执行cur就是出列者删除后然后cur移到下一个。正确。或者更常见的写法从cur开始每次先cur找到下一个存活计数k次? 取决于计数起点。为了避免错误我们可以采用list版本list的for (int step 1; step m; step)是正确的因为it当前指向报数1的人移动m-1步到达报数m的人。list代码是好的。数组模拟应当采用类似逻辑。上面的数组代码初始cur1。for i1; im; i 移动m-1步到出列者删除然后cur找下一个存活作为新起点。这是正确且直观。我在草稿里写的是错误代码不能放进博文。需要重写博文中的数组代码。我们重新提供正确数组代码#include iostream #include vector using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; while (cin n m) { vectorbool alive(n 1, true); int cnt n; int cur 1; // 当前报数的人 while (cnt 1) { // 从cur开始报数1所以只需要移动m-1步到报数m的人 for (int i 1; i m; i) { do { cur; if (cur n) cur 1; } while (!alive[cur]); } alive[cur] false; cnt--; // 删除后从下一个人开始下一轮报数 if (cnt 1) { do { cur; if (cur n) cur 1; } while (!alive[cur]); } } for (int i 1; i n; i) { if (alive[i]) { cout i endl; break; } } } return 0; }验证n5,m3 cur1。for i1到2 i1: do cur-2 alive true; i2: do cur-3 alive true; alive[3]false; cnt4; cnt1 do cur-4 alive true; cur4。 下一轮从4开始报数1。继续for i1到2 i1: cur-5 true i2: cur-1 true (因为alive[1] true) 删除1alive[1]false; cnt3; cnt1 do cur-2 true; cur2。 下一轮从2报数。for i1: cur-4 true i2: cur-5 true 删除5alive[5]false; cnt2; cnt1 do cur-2 true; cur2。 下一轮从2报数。for i1: cur-4 true i2: cur-2 true 删除2alive[2]false; cnt1; 最后alive[4]true输出4。正确。好。博文中不能用错误代码。修正后的代码可以。链表代码中list的erase我们验证正确。n5,m3list [1,2,3,4,5], itbegin (1)。for step1; step3; step: step1: it -2; not end; step2: it -3; 结束循环。erase(it)删除3iterase返回下一个4if end no。剩余[1,2,4,5], it4。下一轮从4报数1实际上删除3后从4开始报1正好it指向4。for step1: it-5; step2: it-1; 删除1it指向2。剩余[2,4,5], it2。下一轮从2报数正确。等等list中迭代器回绕it到end要设begin但list的end在5之后删除1后it指向2。如果中途到end需要设begin。代码中每次后检查if(itend) itbegin。正确。最终剩4。好。递推代码没问题。在博文3.1节中原来写的数组代码是错误的必须替换为正确版本并解释为什么for要m-1删除后为什么还要移动到下一个。这一点很重要。这样反而更实用了。我在输出最终博文时不要包含错误代码。注意。3.1 重新书写先给一个比较稳的版本适合绝大多数基础题数据范围。我用的思路是数组标记加‘先移动后判断’。 然后提供正确代码。之后解释为什么是m-1而不是m还有删除后为什么要再走一步到下一个存活者。还要提到m1情况。这样章节内容增加。3.2 链表版正确 递推版正确。3.3 输出出列顺序要调整数组代码在删除时cout。3.4 input details。这些内容需要保留和扩展。现在整体重新构思博文保证没有错误。让我们重新编写完整博文。注意避免之前错误遗留。可以使用复杂度和总结表格。禁用mermaid。表格允许。表格示例| 解法 | 时间复杂度 | 空间复杂度 | 适合场景 | | 数组模拟 | O(nm) | O(n) | n小、代码直观 | | 链表模拟 | O(nm) | O(n) | 练习迭代器 | | 数学递推 | O(n) | O(1) | n大、求最后幸存者 |这符合要求。现在编写完整最终稿。注意每个段落至少150字。自然分段。目标最终约7000-8000字。这里需要尽量详细。接下来输出全文。注意格式不要主标题直接 from 开头段落 然后 ## 1. 等。在开头段落之前是否需要一个标题要求不需要主标题直接从二级标题开始。所以开头段落直接是文本然后 ## 1. ... 可以。我们这样。 东华OJ的基础题列表里第41题叫“环”。我第一次看到这个题名的时候还以为是数据结构里的链表成环判断结果点进去才发现题面写的是n个人围成一圈从1号开始报数报到m的人出圈然后从下一个人重新报数反复执行直到剩一个人输出这个人的编号。这不就是经典的约瑟夫环么。用C解这道题既能练到循环模拟又能把递归和递推的思路一起打通而且这道题还经常被拿来当面试算法题的变体值得认真写一写。这篇文章我就照着我在东华OJ上的做题经验把从暴力模拟到数学递推的几种解法、完整可提交代码、容易踩的坑以及相关扩展全部盘一遍。1. 题目到底在考什么从“环”到约瑟夫环1.1 题面核心与输入输出风格先聊题面。常见题干是有n个人围成一圈编号从1到n。从第1个人开始从1开始报数报到m的人离开圈子下一个人从1继续报数。问最后留下的人的编号是多少。输入一般是一行两个整数n和m输出一个整数。东华的评测机多组输入是常态所以代码里要写成while (cin n m)这种有些版本会用0 0作为结束标志。这道题的关键在这两个数字的范围。我见过有的版本n最大到1000模拟随便过也有的版本n能到10万甚至百万这时候如果还用链表硬转十有八九会超时。所以基础题不只是让你AC还得琢磨一下复杂度。东华OJ这道“环”在基础题里的位置不算靠后意味着你至少已经会数组、循环、函数这些基础语法了正好可以用它来检验自己对“抽象过程”的理解。1.2 为什么它是“基础题分水岭”我个人觉得东华OJ把它放在基础题里是有点“心机”的。表面上看你只要会while循环和数组就能写但实际上它考察了三个层次的能力第一层是会模拟理解什么叫“循环”比如下标越界取模回绕第二层是会选用合适的数据结构比如循环链表、std::list、vector的删除操作第三层是能发现数学规律直接递推。很多刷题的人第一层就过了但第三层才是这个题真正的闪光点。从编码量来说模拟法的代码大概30到50行递推法几行就写完。差距这么大根源在于你有没有跳出“翻译题面”的惯性。我后来带过几个学弟发现他们最常犯的错就是把题目当成流程说明书一步步照做却从不去想“每次删除后下一轮的人是怎么重新编号的”。一旦开始思考重新编号递推公式自然就出来了。这就是这道题真正的价值所在。2. 三种解法逐层拆解从模拟到数学2.1 循环链表模拟最贴近题面的思路最直观的写法就是真的维护一个环。C里可以用std::list 存1到n然后拿迭代器从头开始走。每走m-1步就删除当前节点然后从下一个节点继续。这个思路几乎就是题面的翻译适合用来建立直观感觉。需要注意的点std::list不是随机访问容器不能直接下标只能用迭代器。走到end()时要立刻赋值为begin()这样才能真的“转圈”。删除节点后迭代器会失效但erase会返回下一个有效迭代器所以删除后要马上接住这个返回值。我见过很多人写了一个类似it people.erase(it)之后又在else分支里it结果删除时跳过了一个人。这种细节等会儿在坑点章节细聊。链表模拟的复杂度是O(n*m)因为每删除一个人都要走m步一共要删除n-1个人。如果n和m都不大这是最好理解的解法。但千万要记住它只是“直观”不是“优秀”。你以为你在用链表模拟环其实本质上还是在暴力扫描只是把数组换成了链表而已。2.2 数组标记模拟常数小代码更简单不想用链表的话用数组加标记也可以。开一个vector alive(n 1, true)然后循环找“下一个还活着的人”。用一个cur表示当前位置每次报数其实是数过m个存活节点。每次删除就把alive[cur]设为false然后cur继续往下找找到下一个活着的节点作为新一轮的起点。这个解法优势是代码直观不容易出现迭代器失效的问题缺点是当m很大时每个m都需要扫描很多已经被删掉的空位最坏情况一样是O(n*m)但常数比链表小。东华OJ基础题的数据量用这个写法通常也能过。不过既然要刷题还是建议一步到位看2.3的递推。我更推荐数组标记法作为“模拟类的标准答案”因为不需要处理链表迭代器出错概率更低。关键是要理解“先移动后判断”的循环结构当前人已经报过数了所以第一步一定是先移动到下一个人再检查他活着没。很多人在这一步错位导致结果差一。我们后面代码里会详细展示。2.3 数学递推O(n)的终极解法约瑟夫环有一个非常优雅的递推公式可以做到O(n)。这里说一个很多人第一次看不懂的推导。我们从最后剩下1个人的时候往前推。假设当前圈子大小为i最后幸存者在“以0为起始编号”的方案里的编号是f(i)。当圈子从i-1扩张到i时我们需要把上一次幸存者的编号平移m位再对i取模。理由是每一轮淘汰一个人之后环的起点会向后偏移m个位置所以反过来当人数增加一人的时候幸存者的编号就要补偿这m个位置的偏移。递推式是f(1) 0f(i) (f(i-1) m) % i, i 2最后f(n)是以0为基准的编号输出f(n)1就是1到n编号下的答案。这个公式适合背但更重要的是理解“重新编号”的视角。随便拿n5、m3手算一遍模拟出来的幸存者是4号用递推算ans从0开始i2时(03)%21i3时(13)%31i4时(13)%40i5时(03)%53最终ans14完全一致。自己算过一遍之后比直接背公式踏实得多。3. 实操过程与C代码实现3.1 完整可提交代码数组模拟版先给一个比较稳的版本适合绝大多数基础题数据范围。我用的思路是数组标记加“先移动后判断”。#include iostream #include vector using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; while (cin n m) { if (n 0 m 0) break; vectorbool alive(n 1, true); int cnt n; int cur 1; // 当前报数的人 while (cnt 1) { // cur已经报了1所以只需要再移动m-1步就找到报数m的人 for (int i 1; i m; i) { do { cur; if (cur n) cur 1; } while (!alive[cur]); } alive[cur] false; cnt--; // 删除后从下一个人开始下一轮报数 if (cnt 1) { do { cur; if (cur n) cur 1; } while (!alive[cur]); } } for (int i 1; i n; i) { if (alive[i]) { cout i endl; break; } } } return 0; }这个代码的坑点有两个。第一个是for循环只走m-1步因为cur本身就站在报数1的人身上走到报数m的人只需要m-1次移动。如果写成for (int i 1; i m; i)结果就会多移动一步删除错人。第二个坑是删除之后处理cur此时停在刚被删除的位置下一轮报数必须从它的下一个活人开始所以要先做一次do-while把cur挪到下一个存活节点。如果漏掉这一步下一轮会把被删掉的人重新当成起点结果必错。m1的情况也不用慌。for循环一次都不执行直接删除cur然后cur移到下一个活人逻辑完全正确。你可以自己拿n5、m1跑一遍输出应该是5。3.2 链表版和递推版代码对比链表版我也贴一份重点展示erase的正确用法#include iostream #include list using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; while (cin n m) { if (n 0 m 0) break; listint people; for (int i 1; i n; i) people.push_back(i); auto it people.begin(); while (people.size() 1) { for (int step 1; step m; step) { it; if (it people.end()) it people.begin(); } it people.erase(it); if (it people.end()) it people.begin(); } cout people.front() endl; } return 0; }注意这里for循环同样只走m-1步因为it当前已经站在报数的人身上。erase之后的返回值是下一个有效迭代器所以不需要再手动。如果自己画一个链表加断点跟一遍会发现这样写非常顺。list的erase在删除后会自动释放内存不用你去关心。递推版代码最短适合求最后幸存者#include iostream using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; while (cin n m) { if (n 0 m 0) break; int ans 0; for (int i 2; i n; i) { ans (ans m) % i; } cout ans 1 endl; } return 0; }这里如果n1for循环不执行ans保持0输出1正好是正确结果不需要特判。递推版最容易被忽略的地方是最后输出必须加1因为全程用的是0起始编号。代码短反而容易因为“少写一个1”而错我自己都犯过好几次。3.3 如果题面要求输出出列顺序怎么办有些版本的约瑟夫环不是求最后一个人而是要求按顺序输出所有出列的人。这时候递推法就派不上用场了因为递推只能告诉你最终幸存者编号却不知道中间每一步出列的是谁。只能老老实实模拟。用数组模拟改起来很简单在删除alive[cur] false之后立刻cout cur 但要注意格式最后一个数字后面不能有空格。更稳妥的做法是开一个vector answer把出列编号收集起来最后统一输出。链表版也是类似就在erase之前把*it存入answer。以后如果刷到洛谷P1996你会发现题目就是让输出出列顺序。所以两套模拟代码最好都熟悉别只背一个递推公式就完事。3.4 提交时容易忽略的输入输出细节我说几个在OJ上实际会遇到的坑多组输入一定写成while (cin n m)不要只读一次。结束标记很多题目用0 0表示输入结束如果不加if (n 0 m 0) break程序会把0和0当成真实数据去模拟轻则输出错误重则数组越界崩溃。输出换行每个输出后记得带\n不要多打空格。关闭同步开头写上ios::sync_with_stdio(false)和cin.tie(nullptr)数据量大时能省下不少时间。这是C刷题的标准动作别懒得写。4. 常见问题与排查技巧实录4.1 为什么我的链表写在数据量大时慢到怀疑人生链表模拟每一步删除一个节点需要走m步删除n-1次复杂度O(n*m)。如果n100000m50000那就是50亿次节点移动不管用什么语言都基本是超时。这没法靠小优化解决只能换递推。这也是我反复强调递推公式的原因。但如果题面本身n比较小比如东华基础题常见的n 100链表模拟非常稳。关键在于先判断数据范围再选算法不要一套模板打天下。我看过很多新手拿到题根本不看数据范围上来就写最“像”题面的代码结果是真被卡到怀疑人生。先看n和m的范围再决定用哪种解法这个习惯要尽早养成。4.2 迭代器失效和死循环std::list的erase在C11里会返回下一个迭代器。删除后如果不接住返回值原来的it就作废了这时候再it是未定义行为程序可能直接崩也可能跳过一个节点甚至死循环。我见过一种错法删除人之后还在循环末尾写了一个it结果每隔一个节点跳过一个人最后输出完全不对。排查方法很简单在循环里加一个计数器超过n*m次还没结束就是死循环。或者把删除的人打印出来和手算结果对照。每次写链表题我都建议先跑n5、m3这个小样例手动算出出列顺序是3、1、5、2、4然后再看程序输出这样能快速定位问题。4.3 报数起点和mn的问题为什么有时候答案差1多半是报数起点理解错了。题目说“从第1个人开始报数报到m的人出列”那么第1个报数的人计数为1数到m的人是第m个人。如果你实现的时候先移动一步再开始计数结果就变成了一开始就数了两个人等于把m当成了m1。链表和数组模拟都要注意在移动步数上报数1的人本身贡献了一个计数所以只需要移动m-1次。另外m可能比n大。数组模拟和链表模拟的循环里要反复绕圈不要担心m太大只要循环次数跟m相关就好。递推公式里直接(ansm)%im多大都不怕因为取模会把多余的整圈去掉。这里有一个基础常识如果m是n的整数倍相当于转了几圈之后又回到起点取模处理最合适。4.4 用vector erase的隐性性能炸弹有人图省事用vector 存人然后用erase删除。这样每一轮删除都会把后面所有元素往前挪平均O(n)总复杂度O(n^2)。数据量小无所谓数据量一大就等着超时。而且vector erase之后的迭代器失效问题更严重比list难处理多了。所以我的建议是要么用list做真正的链表删除要么用数组标记法要么直接递推。vector的erase在约瑟夫环里属于“看起来能用实际最坑”的写法。4.5 递推法输出编号忘记加1递推公式算出来的是从0开始的编号直接输出ans会在n5、m3时得到3正确应该是4。所以忘记加1是递推法最常见的错误。数组和链表法因为一开始存的就是1到n不会错。建议在代码里加一行注释输出ans1提醒自己。另外递推法里ans和m相乘再取模理论上ansm不会溢出int但如果遇到极端数据n和m都接近int上限最好还是把中间变量声明为long long避免不必要的风险。5. 扩展与延伸环问题其实有一大家子5.1 变体一从指定编号K开始报数如果题目改成“从第K个人开始报数”最简单的处理方式是在递推完得到编号后做个偏移。标准递推默认从0开始如果从K开始相当于将整个环旋转最终幸存者编号可以这样算((ans K - 1) % n) 1这里的ans是原来从0或1开头算出来的结果更严谨的做法是直接用模拟法把初始位置设为K这样不容易错。面试时如果被问到先说明“偏移量”的概念再用一个简单例子验证。我记得n5、m3、K2时正确结果是5拿上面的公式算一遍也能对上。但说实话这种变体在OJ里不常见笔试倒是可能考理解原理比背公式重要。5.2 变体二每轮m会变化有些题不是固定m而是每一轮报数的上限是数组m[i]比如第一轮报到3的人出列第二轮报到4的人出列。这时递推公式还能用吗能用但公式要改成反着取下标f(i) (f(i-1) m[n-i1]) % i。这个“反着取”的下标非常容易出错不如直接用链表模拟清晰。所以递推很美但它不是万能的学会判断题型很重要。5.3 变体三返回出列序列上面说过洛谷的P1996就是要求输出出列序列。这种题几乎只能模拟但如果你只是想要所有出列顺序还有一种进阶做法是使用树状数组或线段树维护“第k个存活的人”把复杂度优化到O(n log n)。新人先不用碰能写好链表模拟已经很不错了。从基础题到进阶题路径是一步步来的。5.4 从东华OJ到面试这道题的现实价值我后来参加技术面试遇到过好几次类似题比如“100个人围成一圈从1开始报数报到7的人退出求最后剩下的是几号”。这种题就是约瑟夫环的换皮。如果你只记得模拟面试官追问一句“n是10^9怎么办”就直接卡壳。但你要是能写出行数很少的递推并且能讲清状态转移的推导印象分完全不一样。所以别把东华OJ基础题当成“过了就好”多想想为什么后面会很受益。我也在写题解时整理过一个简单的复杂度对照表送给有需要的朋友解法时间复杂度空间复杂度最适合的场景数组标记模拟O(n*m)O(n)n小、需要输出出列顺序链表模拟O(n*m)O(n)练习迭代器、理解环结构数学递推O(n)O(1)n大、只求最后幸存者这张表看起来很朴素但每次写约瑟夫环前我都会在脑子里过一遍数据规模落在哪个区间决定了你到底该用哪一列。我在刷东华OJ基础题的时候这道“环”其实是我第三次才彻底搞明白的题。第一次用数组硬模拟勉强过了第二次学了list觉得自己懂数据结构了第三次看到递推公式才意识到前面几次都是“用代码翻译题目”根本没有理解本质。现在再看这道题我反而觉得它最值得练的不是AC而是“从模拟到归纳”的思维转变。最后分享一个实用小习惯不管用哪种解法先手动跑n5、m3这个用例把结果记下来再对着代码单步调试。这样能最快找到报数起点差一、迭代器失效这类隐蔽问题。希望能帮到正在刷东华OJ的你。