本文主要是介绍UVA-11988 Broken Keyboard (a.k.a. Beiju Text)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：https://vjudge.net/problem/UVA-11988
题意：你有一个破损的键盘，键盘上的所有键都可以正常工作，但是有时Home键或者End键会自动按下，但你并不知道这个问题，而只是专心打稿子，你对自己的打字水平太自信甚至连显示屏都没有打开，打完之后当你打开显示屏的时候，在你面前的稿子杂乱不堪，给你Home键 和End键自动按下的位置，让你复原文本。输入杂乱的文本，“[”代表Home键，“]”代表End键。
分析：本题最简单的想法就是用数组来保存这段文字，通过判断字符将文本在数组中频繁移动，扫完所有的文本即可恢复原文本。但是在数组中频繁移动元素的位置是非常耗时的，此种做法虽能得出正确结果，但是最终结果会TLE。解决方案是采用链表。每输入一个字符，就把他存起来，设输入字符串是s[1~n],则可以采用next[i]表示当前显示屏s[i]右边的字符编号。为了方便，常常在链表第一个元素之前放一个虚拟节点。
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN=100005;
int nex[MAXN];
char s[MAXN];int main() {//freopen("in.txt", "r", stdin);while(scanf("%s",s+1)!=EOF) {int len=strlen(s+1);int cur=0,last=0; //用cur表示光标位置，last表示显示屏最后一个字符的位置nex[0]=0;for(int i=1; i<=len; i++) {if(s[i]=='[') cur=0; //若遇到Home键，光标回到行首else if(s[i]==']') cur=last; //若遇到End键，光标移动到行尾else {nex[i]=nex[cur];nex[cur]=i;if(cur==last) last=i;//更新最后一个字符的编号cur=i;//移动光标}}for(int i=nex[0]; i!=0; i=nex[i])cout<<s[i];cout<<endl;}return 0;
}
这篇关于UVA-11988 Broken Keyboard (a.k.a. Beiju Text)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
