11368: 【原1368】丁姐的猴子

题目

题目描述

author: SSY 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1368

Description

丁姐和二哥一样养了很多猴子，每只猴子脖子上都挂着一个数字号码牌（数字可能重复但是不重要），一天他和这些猴子完游戏。一开始时有n只猴子围成一圈，猴子的号码牌按顺序为1~n。从当前猴子开始1~k报数，报到k后可能由两种操作：

①报到k的猴子从圈中出去，由刚刚退出的猴子的下一只猴子再开始报数。

②在报到k的猴子后边加一只号码牌为w的猴子，由刚刚加入的猴子开始再报数。

初始时从编号为1的猴子开始报数，求最后圈内所有猴子的号码牌上数字之和。

Input Format

输入第一行两个数，分别为初始时的猴子数量n和操作数量m。

接下来m行，每行描述一个操作：

0 k，删除报到k的猴子。

1 k w，在报到k的猴子后面加入一只号码牌为w的猴子。

保证圈内至少有一只猴子。

Output Format

输出一行，一个数，表示圈内剩下猴子号码牌之和。

Sample Input

Sample Output

说明

对于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)]

yyong119's solution

#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;
}