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+1)!=EOF){
        int len=strlen(s+1);
        next[0]=0;last=cur=0;
        for(int i=1;i<=len;i++){
            if(s[i]=='[')cur=0;
            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[0];i;i=next[i])
         printf("%c",s[i]);
        printf("
");
    }
    return 0;
}