CODEVS4650 破损的键盘

传送门

题目大意：一个字符串，将[]内的字符提前。

题解：链表，数组元素高效交换

cur表示目前元素插入下标为cur的元素后面。

所以，假设目前把下标为i的元素插到cur后面。

那么，next[i]=next[cur]，为cur后面的元素成为i后面的元素

next[cur]=i，cur后面的元素就是i了。

如果遇到'['，说明要把后面到'['插到开头了，cur赋值为0，

last表示最后输出答案的下标。

如果遇到']'，那么cur=last，继续从最后一个元素开始插入。

代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#define maxn 100009

using namespace std;

char s[maxn];

int cur,last,next[maxn];

int main(){

    while(scanf("%s",s+)!=EOF){

        int len=strlen(s+);

        next[]=;last=cur=;

        for(int i=;i<=len;i++){

            if(s[i]=='[')cur=;

            else if(s[i]==']')cur=last;

            else{

                next[i]=next[cur];

                next[cur]=i;

                if(cur==last)last=i;

                cur=i;

            }

        }

        for(int i=next[];i;i=next[i])

         printf("%c",s[i]);

        printf("\n");

    }

    return ;

}