洛谷--链表

约瑟夫问题

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

首先,有一个叫"循环链表"的东西非常适合这道题目

比如样例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个

用数组也可以模拟链表

我们可以定义一个数组,来存储每个元素的下一个元素

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

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int []arr = new int[n];
        for(int i = 0;i<n-1;i++){
            arr[i] = i+1;
        }
        arr[n-1] = 1;//最后一个的下一个是第一个,特殊处理

模拟出圈过程,比如第3个人出圈时,把2的下一个从3改为4,下次到这里从2就会直接到达4,从而跳过3

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

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

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

我们要访问的数组下标(也就是人的位置) 正式arr[下标]的值,也就是说 p = arr[p]

现在来看细节:最好不要让p到达出圈人的位置,因为出圈人的位置是要被跳过的,p留在这里很不方便

把p放在出圈人的前一个位置就可以,输出的话再输出p的下一个,然后把next[p] 改成next[next[p]]

除此之外,还有一个小问题既然是把p放到出圈人的前一个位置,那么把p = next[p]执行(m-1)次,但第一个如果从1开始,执行(m-1)次还是到了出圈人的位置.

int p = n-1;//从最后一个人的前一个开始
        //建立p变量(类似指针)来遍历数组,初始化为0
        for(int i= 1;i<=n;i++){//n个人出圈n次
            for(int j = 1;j<m;j++){
                //移动(m-1)次,到达出圈人人的前一个位置
                p = arr[p];//p到达下一个
            }
            //此时p到达除权日的前一个位置
            System.out.print(arr[p]+1);//输出出圈人的位置 +1是因为我们数组下标从0开始的
            System.out.print(" ");
            arr[p] = arr[arr[p]];//把p指向p的下下个,跳过(删除出圈人)
        }

完整代码:

import java.util.Scanner;

public class yjy {
    public static void main(String[] args) {
        // 约瑟夫问题
        // -- 循环链表 --
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int []arr = new int[n];
        for(int i = 0;i<n-1;i++){// 0 1 2 3 4.. 9
            arr[i] = i+1;      //   1 2 3 4 5...0
        }
        arr[n-1] = 0;
        int p = n-1;
        for(int i = 0;i<n;i++){//n个人出列
            for(int j = 1;j<m;j++){//(m-1)
                p = arr[p];//下一个
            }
            //待删除点的前一个
            System.out.print(arr[p]+1+" ");
            //跳过这个点
            arr[p] = arr[arr[p]];
        }

    }
}

队列安排

手拉手的过程

#include <iostream>
#include<bits/stdc++.h>
using namespace std;

const int mx = 1e5 + 10;

struct Student {
    int left, right; // 每个同学的“左右手”
    bool removed;    // 表示同学是否被移除
} students[mx] = { 0 };

void add(int position, int id, int side) // 新增同学
{//position 参考同学
    if (side == 0) { // 左边
        students[id].right = position;
        students[id].left = students[position].left;
        students[students[position].left].right = id;
        students[position].left = id;
    }
    else { // 右边
        students[id].left = position;
        students[id].right = students[position].right;
        students[students[position].right].left = id;
        students[position].right = id;
    }
}

int main() {
    int n, m;
    cin >> n;

    // 初始化
    students[0].right = 1; students[0].left = 1;
    students[1].left = 0; students[1].right = 0;
    students[1].removed = false;

    // 依次插入同学
    for (int i = 2; i <= n; ++i) {
        int position, side;
        cin >> position >> side;
        add(position, i, side);
        students[i].removed = false;
    }

    // 读取需要移除的同学编号并标记
    cin >> m;
    for (int i = 0; i < m; ++i) {
        int id;
        cin >> id;
        students[id].removed = true; // 将该同学标记为移除
    }

    // 输出结果
    for (int i = students[0].right; i != 0; i = students[i].right) {
        if (!students[i].removed) // 输出未标记的
            cout << i << " ";
    }
    cout << endl;

    return 0;
}