【POJ】1068 Parencodings 括号匹配 模拟 规律

Problem: 1068 User: angrad 
Memory: 136K Time: 0MS 
Language: C Result: Accepted 

题意：p数组的意思是每个数字所在处及其前面有多少个左括号。
    而w数组的意思是数字所在位置的右括号能和左边的第几个左括号匹配 
如S            (((()()())))
P-sequence       4 5 6666
W-sequence       1 1 1456
由P求w只需找到另一个数组存储每个右括号前面有多少个左括号，我这里用a数组表示
则       a应该为 4 1 1000
a[i+1] =p[i+1] - [pi];(i=-1, 0, 1, ...n-2)code中我直接用到两个临时变量temp1，temp2在输入P的时候就换好了。
标记b数组，为0表示未配对的右括号，根据a中每个对应它前面的左括号数来计算并存入b数组。
a、b数组的变化, x为当前位置 
---------     ---------     ---------  ---------  ---------  --------- ---------
a：411000     a: 311000     a: 301000  a: 300000  a: 200000  a: 100000 a: 000000
                 x              x           x           x           x          x 
b：000000      b: 100000      b: 110000   b: 111000   b: 111400   b: 111450  b: 111456

---------     ---------     ---------  ---------  ---------  --------- ---------  

#include <stdio.h>
#include <stdlib.h>

#define MAX 20

int main()
{
   int t,n, i, j, a[MAX],b[MAX], temp1, temp2;
   scanf("%d", &t);
   while(t--)
   {
       scanf("%d", &n);
       temp1 = 0;
       memset(a, 0, sizeof(a));
       memset(b, 0, sizeof(b));
       for(i=0;i<n;i++)
       {
           scanf("%d", &a[i]);
           //输入的同时直接改变a数组
           temp2 = a[i];
           a[i] -= temp1;
           temp1 = temp2;
       }

       for(i=0;i<n;i++)
       {
           if(!b[i])
           {
               if(a[i] > 0)
               {
                   a[i]--;
                    b[i] = 1;
               }
               else
               {
                    b[i] = 1; //b[i]左移找左括号，从1计数
                   j = i;
                   while(!a[--j])
                   {
                        b[i]++;
                   }
                    b[i]++;
                   a[j]--;
               }
           }
       }
       //避免输出多余空格，先输出b[0]
       printf("%d",b[0]);
       i = 1;
       while(i <n)
       {
           printf(" %d",b[i++]);
       }
       printf("n");
   }

   return 0;
}

2011-03-31 14:48 发表于百度空间，今搬至CU。