题解 AT1409 【掲示板】

Kevin_Zhen · 2020-03-11 19:58:25 · 题解

链表题解

题目链接 AT1409

题目大意

给你一个序列 1-n，进行 m 次操作，每次将值为 a 的一项移到序列首位。

变量介绍

3. 结构体 node，data 记录此节点的值，next 记录前驱，prev 记录后继。

解题过程

1.初始化

a[0].next = 1; 
for (int i = 1; i <= n; ++i) {
    a[i].data = i;
    a[i].next = i + 1;
    a[i].prev = i - 1;
}

对链表进行初始化（包括赋值、记录前驱和后继），注意 a[0].next 也要赋值，用于记录队首元素。

2.修改操作

int k = readInt();
a[a[k].next].prev = a[k].prev;
a[a[k].prev].next = a[k].next;
a[k].next = a[0].next;
a[k].prev = 0;
a[a[0].next].prev = k;
a[0].next = k;

将修改节点 k 取出并插入队首，并及时更新 k 的前驱的后继、后继的前驱，k 的前驱和后继，0 号节点的后继的前驱和 0 号节点的后继。文字描述比较绕，可以结合代码理解。

3.输出

int s = a[0].next;
while (a[s].data != 0) {
    printf("%d\n", a[s].data);
    s = a[s].next;
}

遍历整个链表，输出每一个节点的值。

4.时间复杂度

时间复杂度 O(n)。

AC CODE

#include <iostream>
#include <cstdio>
#include <cctype>

inline int readInt() {
    int s = 0, c;
    while (!isdigit(c = getchar()));
    do s = s * 10 + c - '0';
    while (isdigit(c = getchar()));
    return s;
}

struct node{
    int data = 0;
    int prev, next;
} a[100010];

int n = readInt(), m = readInt();

int main() {
    a[0].next = 1; 
    for (int i = 1; i <= n; ++i) {
        a[i].data = i;
        a[i].next = i + 1;
        a[i].prev = i - 1;
    }
    for (int i = 1; i <= m; ++i) {
        int k = readInt();
        a[a[k].next].prev = a[k].prev;
        a[a[k].prev].next = a[k].next;
        a[k].next = a[0].next;
        a[k].prev = 0;
        a[a[0].next].prev = k;
        a[0].next = k;
    }
    int s = a[0].next;
    while (a[s].data != 0) {
        printf("%d\n", a[s].data);
        s = a[s].next;
    }
    return 0;
}

感谢观赏！