题目连接(本题目链接失效内容同《围圈报数》)：http://ybt.ssoier.cn:8088/problem_show.php?pid=1418
围圈报数链接：http://ybt.ssoier.cn:8088/problem_show.php?pid=1334
从队列到循环单链表写了一下午都写不出来，网上查了半天题解发现多数用到<vector>而且还用到迭代器（https://blog.csdn.net/u011954296/article/details/51351982），对于我那群没学过的娃来说比较难理解，还有用牛逼的数学公式推到出来只用20行代码就解决问题，反正我是想不到。晚间在家看孩子时，灵光一现，这个是不是可以用“双向循环链表”就可以克服下午遇到的种种问题，于是迅速花半个小时写出，代码很短，理解“双向循环链表”就很容写出了，加上详细注释，独家出品，如有雷同罚款100，仅供参考。但个人还是觉得这种数学的推理是值得推介的（https://www.cnblogs.com/jiu0821/p/4587507.html），一题多解，解后看别人题解，一定是提升算法学习非常有效的学习方法，建议大家多多看看别人的代码。
1 1 #include<iostream> 2 2 using namespace std; 3 3 struct node{ 4 4 int pre;//存储之前节点下标 5 5 int x;//当前可以数得数 6 6 int nex;//存储之后节点下标 7 7 }q[1000100];//自定义循环双向链表的数据结构 8 8 //思考为什么不能用单向循环链表??? 9 9 int main() 1010 { 1111 int n; 1212 cin>>n; 1313 for(int i=1; i<=n; i++)//构造循环双向链表 1414 { 1515 cin>>q[i].x; 1616 if(i==n) q[i].nex=1; 1717 else q[i].nex=i+1; 1818 if(i==1) q[i].pre=n; 1919 else q[i].pre=i-1; 2020 } 2121 //for(int i=1; i<=n; i++)cout<<q[i].pre<<q[i].x<<q[i].nex<<endl; //用于测试构造的循环双向链表是否成功 2222 int now=1;//从第一只猴子开始 2323 while(q[now].nex!=now && q[now].pre!=now)//当只剩下最后一只猴子时，他的之前节点和之后节点都指向它自己，于是他就是大王 2424 { 2525 int xx=now, yy=q[now].x;//当前开始计数的猴子编号 2626 for(int i=xx; i<xx+yy-1; i++) now=q[now].nex; // 从当前猴子的节点开始报数到<被删除猴子>的节点，此时now为 <被删除猴子>的节点的下标 2727 2828 q[q[now].pre].nex=q[now].nex;//<被删除猴子>之前节点的之后节点更改为<被删除猴子>的之后节点 2929 q[q[now].nex].pre=q[now].pre;//<被删除猴子>之后节点的之前节点更改为<被删除猴子>的之前节点 3030 3131 now=q[now].nex;//更改now为删除猴子的下一个节点重复 3232 3333 } 3434 cout<<now; 3535 return 0; 3636 }
AC后开心的去睡觉觉~~~