uva 11988

题意：有一个键盘坏了会在你不知道的情况下按下home或者end 给你这个键盘的实际输入要求输出显示器上的实际显示

解析：输入最大5MB 直接数组检索肯定会超时，用 数组模拟链表

　　　　next数组表示显示屏中s[i]右边的字符编号，变量cur模拟光标，即当前光标位于s[cur]的右边。

　　　　变量last记录显示屏最后一个字符的下标。

 1 #include <cstdio>
 2 #include <cstring>
 3 using namespace std;
 4 const int N = 100005;
 5 char s[N];
 6 int next[N];
 7 
 8 int main()
 9 {
10     int last, cur;
11     while(~scanf("%s", s+1))
12     {
13         next[0] = last = cur = 0;
14         int length = strlen(s+1);
15         for(int i=1; i<=length; i++)
16         {
17             if(s[i] == '[')    cur = 0;
18             else if(s[i] == ']')    cur = last;
19             else
20             {
21                 next[i] = next[cur];
22                 next[cur] = i;
23                 if(cur == last)    last = i;    //更新最后一个字符编号
24                 cur = i;    //移动光标
25             }
26         }
27         for(int i=next[0]; i; i=next[i])
28             printf("%c", s[i]);
29         printf("
");
30     }
31     return 0;
32 }

使用迭代器求解：

 1 #include <iostream>
 2 #include <string>
 3 #include <list>
 4 #include <iterator>
 5 using namespace std;
 6 
 7 int main()
 8 {  
 9     string line;
10     while (getline(cin, line))
11     {
12         list<char> beiju;
13         list<char>::iterator iter(beiju.begin());
14         for (size_t i = 0; i < line.size(); ++i)
15         {
16             // "Home" key.
17             if (line[i] == '[')
18                 iter = beiju.begin();
19             // "End" key.
20             else if (line[i] == ']')
21                 iter = beiju.end();
22             
23             /** Using a vector<char> works but will get TLE.    
24                 
25                 iter = beiju.insert(iter, line[i]); 
26                 ++iter;
27             */
28             else
29                 beiju.insert(iter, line[i]);                
30         }
31         copy(beiju.begin(), beiju.end(), ostream_iterator<char>(cout, ""));
32         cout << endl;
33     }
34     return 0;
35 }