POJ1068 Parencodings

题目来源：http://poj.org/problem?id=1068

题目大意：

　　S = s1 s2...s2n 是由n对配对的左右括号组成的串. 可以用两种方式对S进行编码： 
　　P-序列： P = p1 p2...pn， pi 表示第 i 个右括号之前的左括号数。 　　
　　W-序列：W = w1 w2...wn， wi 表示从与第 i 个右括号匹配的左括号位置处开始计到该右括号是第几个右括号。

   下面是一个实例：

	S		(((()()())))

	P-sequence	    4 5 6666

	W-sequence	    1 1 1456

写一个程序将P-序列转换为W-序列。 

输入：第一行t(1<=t<=10)为测试用例数。每两行表示一个测试用例，第一行为序列长度n(1<=n<=20)，第二行为n个数字组成的串，每个数字之间用空格隔开，表示一个P-序列。

输出：每行对应一个测试用例，输出其W-序列，每个数字用之间用空格隔开。

---

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

---

这道题可以当做模拟题来做，先按P-序列还原出括号序列，然后求出W-序列。但是实际上有比这更巧妙的办法：

容易发现p[i] > p[i - 1]时，第i个右括号与第i-1个右括号之间存在左括号，这样这里的左括号就可以直接被第i个右括号匹配，所以wi = 1.

如果p[i] == p[i - 1]，则右括号前面相邻的还是右括号，需要再往前找没有被匹配过的左括号。怎样才能找到尚未被匹配最右边的左括号呢？一种思路是我们用一个数组记录下前面每个右括号前到前一个右括号之间还有多少个左括号没有被匹配。然后遇到需要向前推的时候，从右向左去查看，找到的第一个还有被匹配的左括号就是即将匹配的那一个。每往前查询一步，对应的wi就应加1.基于该方法的代码：

//////////////////////////////////////////////////////////////////////////
//        POJ1068 Parencodings
//        Memory: 248K        Time: 0MS
//        Language: C++        Result : Accepted
//////////////////////////////////////////////////////////////////////////

#include <iostream>

using namespace std;

int main(void) {
    int T, n, p[30], r[30];    
    //p[i]为第i个右括号左边共有多少个左括号
    //r[i]为第i个右括号与i - 1个右括号之间还有几个左括号没有被匹配
    cin >> T;
    while (T--) {
        cin >> n;
        p[0] = r[0] = 0;
        for (int i = 1; i <= n; ++i) {
            cin >> p[i];
            r[i] = p[i] - p[i - 1];
            int j = i, ans = 1;
            while (r[j] == 0) {
                --j;
                ++ans;
            }
            --r[j];
            cout << ans << " ";    
        }
        cout << endl;
    }
    return 0;
}

上面的方法还不是最优的，还有辅助空间O(1)的算法：实际上，令 j = i - 1； 从后往前，遇到最大的 j 满足 p[i] - p[j] >= i - j 就说明与 i 匹配的左括号应该位于 j 之后， j + 1 之前。原因：i 到 j 恰好有 i - j 个右括号，p[i] - p[j] 表示第 j 个右括号到第 i 个右括号之间的左括号数。如果p[i] - p[j] < i - j， 说明 j 之后的左括号都已经被匹配掉了，还需要往前找，第一个满足 >= 关系的 j 后有剩余的左括号。同样 j 每减小1， wi 就增加1. 基于该方法的代码：

//////////////////////////////////////////////////////////////////////////
//        POJ1068 Parencodings
//        Memory: 248K        Time: 0MS
//        Language: C++        Result : Accepted
//////////////////////////////////////////////////////////////////////////

#include <iostream>

using namespace std;

int main(void) {
    int T, n, p[21];
    cin >> T;
    while (T--) {
        cin >> n;
        p[0] =  0;
        for (int i = 1; i <= n; ++i) {
            cin >> p[i];
            int j = i - 1, ans = 1;
            while (p[i] - p[j] < i - j) {
                --j;
                ++ans;
            }
            cout << ans << " ";
        }
        cout << endl;
    }
    return 0;
}