题目连接(本题目链接失效内容同《围圈报数》):http://ybt.ssoier.cn:8088/problem_show.php?pid=1418
围圈报数链接:http://ybt.ssoier.cn:8088/problem_show.php?pid=1334
从队列到循环单链表写了一下午都写不出来,网上查了半天题解发现多数用到
1 #include<iostream>
2 using namespace std;
3 struct node{
4 int pre;//存储之前节点下标
5 int x;//当前可以数得数
6 int nex;//存储之后节点下标
7 }q[1000100];//自定义循环双向链表的数据结构
8 //思考为什么不能用单向循环链表???
9 int main()
10 {
11 int n;
12 cin>>n;
13 for(int i=1; i<=n; i++)//构造循环双向链表
14 {
15 cin>>q[i].x;
16 if(i==n) q[i].nex=1;
17 else q[i].nex=i+1;
18 if(i==1) q[i].pre=n;
19 else q[i].pre=i-1;
20 }
21 //for(int i=1; i<=n; i++)cout<<q[i].pre<<q[i].x<<q[i].nex<<endl; //用于测试构造的循环双向链表是否成功
22 int now=1;//从第一只猴子开始
23 while(q[now].nex!=now && q[now].pre!=now)//当只剩下最后一只猴子时,他的之前节点和之后节点都指向它自己,于是他就是大王
24 {
25 int xx=now, yy=q[now].x;//当前开始计数的猴子编号
26 for(int i=xx; i<xx+yy-1; i++) now=q[now].nex; // 从当前猴子的节点开始报数到<被删除猴子>的节点,此时now为 <被删除猴子>的节点的下标
27
28 q[q[now].pre].nex=q[now].nex;//<被删除猴子>之前节点的之后节点更改为<被删除猴子>的之后节点
29 q[q[now].nex].pre=q[now].pre;//<被删除猴子>之后节点的之前节点更改为<被删除猴子>的之前节点
30
31 now=q[now].nex;//更改now为删除猴子的下一个节点重复
32
33 }
34 cout<<now;
35 return 0;
36 }
AC后开心的去睡觉觉~~~