X龙珠

发表于 更新于 分类于

$Problem’s$ $Website$

X龙珠

$Solution$

运用链表思想，用数组模拟链表，存储一个数据的$next$和$last$(后一个和前一个)，然后类似于贪心，我们从大到小枚举，如果当前的数没有$next$，说明无法输出，如果有，则将它和它的$next$输出，更新一下与这两个数相邻的数的$next$和$last$，然后将这两个数的$next$和$last$清零即可。

$Code$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//Coded by dy.
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define re register
const int Maxn = 1e5 + 10;
int n;
int a[Maxn], nxt[Maxn], lst[Maxn];
int main() { 
    scanf("%d", &n);
    for(re int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
        nxt[a[i]] = i + 1;
        lst[a[i]] = i - 1; 
    }
    nxt[a[n]] = lst[a[1]] = 0;
    for(re int i = n; i >= 1; --i) { 
        if(a[nxt[i]]) { 
            printf("%d %d ", i, a[nxt[i]]);
            nxt[a[lst[i]]] = nxt[a[nxt[i]]];
            lst[a[nxt[a[nxt[i]]]]] = lst[i];
            nxt[a[nxt[i]]] = lst[a[nxt[i]]] = 0;
            nxt[i] = lst[i] = 0;
        }
    }
    return 0;
}

$rp++$