Victordu

這個題目的思路算是模擬過程吧

題目先翻譯一下

讓S=s1 s2 s3...s2n表示一串符合規范的括號串（即每個左括號必有一個右括號相對應）。

這樣的S能用兩種方法來表示（編碼）：

1。用一個整數序列P＝p1p2...pn,其中pi是第i個右括號前的左括號個數

2。用一個整數序列W＝w1w2...wn，其中 wi 是從第 i 個右括號往左數直到遇到和它相對應的左括號時經過的左括號個數（包括與第i個右括號相對應的左括號）。

比如：

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

P: 4 5 6 6 6 6

W: 1 1 1 4 5 6

我們的任務就是將一個p序列轉化為w序列

輸入：

第一個數字t是測試的例子的數目（1<=t<=10）。接下來的是測試例子。每一個例子包含兩行數據，第一行是p序列的數字個數，第二行表示的n個數是p序列，每個數字間用空格格開。

輸出：由t行組成，每行是一個w序列。

代碼如下：
/**********************
Author: WHU_Victordu
Created Time: 2007-12-27
File Name: pku1068.cpp
  Description: 
   **************************/
#include <stdio.h>
#include<string.h>

char qut[41];
int p[21],used[41];

int main()
{
    int t,n,i,tmp,j,k,rightcnt,cnt;
    scanf("%d",&t);
    while(t--)
    {
      scanf("%d",&n);
      for(i=0;i<n;i++)
       scanf("%d",&p[i]);
      
      tmp=0;k=0;
     
      for(i=0;i<n;i++)
      {
        tmp=p[i]-tmp;
        for(j=0;j<tmp;j++)
        {
          qut[k++]='(';
        }
        qut[k++]=')';
        tmp=p[i];     
      }
     
      qut[k++]='\0';
     
      memset(used,0,sizeof(used));
      rightcnt=0;
     
      for(i=0;i<2*n;i++)
      {
        if(qut[i]==')')
        {
          rightcnt++;
          cnt=1;
          for(j=i-1;j>=0;j--)
          {
            if(qut[j]=='('&&!used[j])
            {
              used[j]=1;
              p[rightcnt]=cnt;
              break;
            }
            else if(qut[j]==')')
            cnt++;
          }
        }
      }
     
      for(i=1;i<n;i++)
       printf("%d ",p[i]);
      
       printf("%d\n",p[n]);
           
    }
}