Description
Let S = s1 s2...s2n be a well-formed string of parentheses. S can be encoded in two different ways:
q By an integer sequence P = p1 p2...pn where pi is the number of left parentheses before the ith right parenthesis in S (P-sequence).
q By an integer sequence W = w1 w2...wn where for each right parenthesis, say a in S, we associate an integer which is the number of right parentheses counting from the matched left parenthesis of a up to a. (W-sequence).
Following is an example of the above encodings:
Write a program to convert P-sequence of a well-formed string to the W-sequence of the same string.
q By an integer sequence P = p1 p2...pn where pi is the number of left parentheses before the ith right parenthesis in S (P-sequence).
q By an integer sequence W = w1 w2...wn where for each right parenthesis, say a in S, we associate an integer which is the number of right parentheses counting from the matched left parenthesis of a up to a. (W-sequence).
Following is an example of the above encodings:
S (((()()())))
P-sequence 4 5 6666
W-sequence 1 1 1456
Write a program to convert P-sequence of a well-formed string to the W-sequence of the same string.
Input
The first line of the input contains a single integer t (1 <= t <= 10), the number of test cases, followed by the input data for each test case. The first line of each test case is an integer n (1 <= n <= 20), and the second line is the P-sequence of a well-formed string. It contains n positive integers, separated with blanks, representing the P-sequence.
Output
The output file consists of exactly t lines corresponding to test cases. For each test case, the output line should contain n integers describing the W-sequence of the string corresponding to its given P-sequence.
Sample Input
2 6 4 5 6 6 6 6 9 4 6 6 6 6 8 9 9 9
Sample Output
1 1 1 4 5 6 1 1 2 4 5 1 1 3 9
Source
题目大意：一组标准的括号（就是每一个左括号的都有且仅有一个右边的对应，符合常理），其编码方式有两种：
P:p[i]表示第i个右括号左边有的左括号数量
W:w[i]表示从与第i个右括号对应的左括号开始至第i个右括号共有右括号的数量
现在给出P串输出W串
解题思路：用b[]统计第i个右括号和第i-1个右括号之间有多少个左括号，然后模拟流程（对于每个右括号向前找
最近左括号，然后在找到的左括号对应区间的b[]减1，依次寻找....
1 #include<iostream> 2 #include<cmath> 3 #include<algorithm> 4 using namespace std; 5 int main(){ 6 int n,a[25],b[25]; 7 int t;cin>>t; 8 while(t--){ 9 cin>>n; //输入 10 for(int i=0;i<n;i++) 11 cin>>a[i]; 12 b[0]=a[0]; //求b[] 13 for(int i=1;i<n;i++) 14 b[i]=a[i]-a[i-1]; 15 cout<<1; //求解并输出 16 for(int i=1;i<n;i++){ 17 for(int j=i;j>=0;j--){ 18 if(b[j]!=0){ 19 cout<<' '<<i-j+1; 20 b[j]--; 21 break; 22 } 23 } 24 }cout<<'\n'; 25 }return 0; 26 }
本文转自beautifulzzzz博客园博客，原文链接：http://www.cnblogs.com/zjutlitao/p/3246004.html，如需转载请自行联系原作者
