丁姐和二哥一样养了很多猴子，每只猴子脖子上都挂着一个数字号码牌（数字可能重复但是不重要），一天他和这些猴子完游戏。一开始时有n只猴子围成一圈，猴子的号码牌按顺序为1~n。从当前猴子开始1~k报数，报到k后可能由两种操作：
①报到k的猴子从圈中出去，由刚刚退出的猴子的下一只猴子再开始报数。
②在报到k的猴子后边加一只号码牌为w的猴子，由刚刚加入的猴子开始再报数。
初始时从编号为1的猴子开始报数，求最后圈内所有猴子的号码牌上数字之和。
输入第一行两个数，分别为初始时的猴子数量n和操作数量m。
接下来m行，每行描述一个操作：
0 k，删除报到k的猴子。
1 k w，在报到k的猴子后面加入一只号码牌为w的猴子。
保证圈内至少有一只猴子。
输出一行，一个数，表示圈内剩下猴子号码牌之和。
5 5
0 2
0 4
1 1 10
0 1
1 2 3
15
对于30%的数据，n<1000，m<1000
对于100%的数据，n<10000, m<10000，w<100000
对于每次操作链表中的元素为（括号里的是下一次报1的猴子）：
5 5 //[(1),2,3,4,5] 0 2 //[1,(3),4,5] 0 4 //[(3),4,5] 1 1 10 //[3,(10),4,5] 0 1//[3,(4),5] 1 2 3//[3,4,5,(3)]
因为会存在相同编号的猴子 所以必须要引入一个新的数组来存储id
in函数少写了最后一行 导致一直没发现错误所在、、、有点傻
#include <iostream> #include <cstdio> using namespace std; typedef unsigned long long ULL; int number[100000+10]; //下表是流水id 内容是身上的编号 int front[100000+10];//流水id的操作 int nex[100000+10];//流水id的操作 //模拟法 void out(int x){ nex[front[x]] = nex[x]; front[nex[x]] = front[x]; } void in(int x,int w){ //此处的W指的是流水id nex[w] = nex[x]; nex[x] = w; front[nex[w]] = w; front[w] = x; } int main(int argc, char const *argv[]) { int M;//猴子的数量M int m; //操作的数量m cin>>M>>m; for (int i = 1; i <= M; ++i) { number[i] = i;//第i个猴子身上的编号是i front[i] = (i==1) ? M : i-1; nex[i] = (i==M) ? 1 : i+1; } int cur = 1;//接下来要报1的猴子编号 int cnt = M;//还有多少只猴子 int K;//数到K要进行操作 ULL res = ((1+M)*M)/2; for (int i = 0; i < m; ++i)//m次操作 { int flag; scanf("%d",&flag); if(flag==0){//要开始删除猴子 scanf("%d",&K); K %= (cnt); if(K==0) K+=cnt; for (int i = 0; i < K-1; ++i) cur = nex[cur];//报数的过程 out(cur); res -= number[cur];//减少剩余猴子所组成的编号之和 cur = nex[cur]; cnt--;//出去一只猴子 }else{ //不删除 只加入 int W; scanf("%d %d",&K,&W); K %= (cnt); number[++M] = W;//流水ID if(K==0) K+=cnt; for (int i = 0; i < K-1; ++i) cur = nex[cur];//报数的过程 in(cur,M);//cur的后面加入一个W res += W; cur = M; cnt++;//出去一只猴子又加入一只猴子 } } cout<<res<<endl; return 0; } /* 5 5 0 2 0 4 1 1 10 0 1 1 2 3 */
【算法学习笔记】59.链表 SJTU OJ 1368 丁姐的猴子
原文：http://www.cnblogs.com/yuchenlin/p/sjtu_oj_1368.html