题解 P1996 【约瑟夫问题】

· · 题解

本魔芋来发题解啦！在此先%%%%%%拜大佬

约瑟夫问题是一个链表的典型题目。为啥要用到链表呢？因为链表的优越性实在太多啦~

首先，有一个叫“循环链表”的东西非常适合这道题

比如样例中n=3，m=10的情况，我们可以建立一个这样的循环链表：

1→2→3→4→5→6→7→8→9→10
↑                  ↓
 ← ← ← ← ← ← ← ← ←

第10个的下一个正好指向第1个，非常符合题目的设定

其次，链表的删除操作非常简便

如果要删掉数组中的一个元素，需要把它之后的所有元素都向前移一个单位，太麻烦了有木有？！而链表恰恰相反，删除数据的操作很简单，只需要改变他们建立的联系就行

什么意思呢？还是用样例解释：当第3个人出圈之前，他们的关系是这样的：

1→2→3→4→5

而出圈之后，他们的关系就成了这样：

   → →
  ↑    ↓
1→2  3→4→5

也就是说，我们把第2个的下一个直接指向了第4个，从而跳过了第3个

链表好归好，但好多小伙伴肯定会像我一样，一提链表，“指针恐惧症”就犯了 对不对？？？

没关系，我们不用指针，用数组也能搞个链表出来！

链表的关键核心在哪？当然在于某个元素与其它的元素建立的联系，通俗易懂来讲，连表可以轻松地操作某个元素的下一个元素是谁。

那咱们只要把每个元素的下一个元素找出来不就行了？我们可以定义一个数组，来存每个元素的下一个元素。数组名就叫......next好了

因为这个题的数据是1~n连续的，所以我们可以用数组的下标来代表数据的内容。比如next[1]=2就是指第1个人的下一个是第2个，以此类推，next[2]=3,next[3]=4.......第10个（还是用样例）的下一个当然是第1个了。

数据 1 2 3 4 5 6 7 8 9 10
next 2 3 4 5 6 7 8 9 10 1

代码实现是这样的

    int n,m;
    cin>>n>>m;//输入，没啥好说的
    for(int i=0;i<n;i++)//为什么从0开始后边会说
        next[i]=i+1;//前n-1个的下一个就是第i+1个
    next[n]=1;//最后一个的下一个是第一个，特殊处理

这样数组的初始化就完成了

模拟出圈过程也不难。比如第3个人出圈时，把2的下一个从3改成4，下次到这里的时候从2就会直接到达4，从而跳过3

数据 1 2 3 4 5 6 7 8 9 10
next 2 ④ 4 5 6 7 8 9 10 1

接下来的任务就是数m个，输出，删掉，再 数m个，输出，删掉......一直重复n次，嵌套循环就能完美解决

首先，咱们定义一个变量p，类似于一个指针。一直重复m次p取下一个的操作。 然后输出出圈人的位置，然后把出圈人的前一个指向他的下下个来跳过出圈人就行了

那么问题来了，如何利用next数组访问下一个呢？

观察咱们列的表表就会发现，我们要访问的数组下标（也就是人的位置）正是next[下标]的值，也就是说

p=next[p];

事已至此，大体的思路就已经搞定了，接下来就是细节的问题。

首先，最好不要让p到达出圈人的位置，因为出圈人的位置是要被跳过的，p留在这里就会很不方便

那咋办呢？？？把p放在出圈人的前一个位置就OK了，输出的话就输出p的下一个，然后把next[p]改成next[p]的下一个，也就是next[next[p]]

除此之外，还要注意一个小小的问题：既然是把p放到出圈人的前一个位置，那就要把p=next[p]执行（m-1）次。但第一次如果从1开始，执行（m-1）次还是到了出圈人的位置，只要把p初始化为0，把next[0]设成1，就万事大吉了，这也是前面代码中next数组的初始化从0开始的原因。

说了这么多，放代码！

    int p=0;
//建立p变量（类似指针）来遍历数组，初始化成0
    for(int i=1;i<=n;i++){//n个人出圈n次
        for(int j=1;j<m;j++){
//移动（m-1）次，到达出圈人人的前一个位置
            p=next[p];//p到达下一个
        }
//此时p到达出圈人的前一个位置
        cout<<p[next]<<" "//输出出圈人的位置;
        next[p]=next[next[p]];
//把p指向p的下下个，跳过（删掉出圈人）
    }

万事俱备，只欠AC，这就是用数组模拟链表，你学会了吗？

#include<iostream>
using namespace std;
int next[1000005];
int main(){
    int n,m;
    cin>>n>>m;//输入n、m
    for(int i=0;i<n;i++)//初始化
        next[i]=i+1;
    next[n]=1;
    int p=0;
    for(int i=1;i<=n;i++){//开始模拟出圈过程
        for(int j=1;j<m;j++)
            p=next[p];//p位置右移
        cout<<p[next]<<" ";//输出出圈人的位置
        next[p]=next[next[p]];//删掉出圈人
    }
    return 0;//功德圆满
}

The End