首页 > 代码库 > poj 1068

poj 1068

   此题多组处理数据,每组输入n个数,每个a[i]代表当前对应的右括号前面共有多少个左括号。
比如:n=6, 4 5 6 6 6 6 。 对应第一个右括号前有4个左括号,第二个右括号前有5个左括号,不过千万不要落下第一个右括号啊,以此类推下去。。。。。。
现在要求输出另一个数组,数组元素为当前右括号包含的括号总数!
比如:(()())
第一个右括号只包含自己,故为 1;
第二个右括号也只包含自己, 故为 1;
第三个右括号包含前面两个括号,再加上自己,故为 3.
所以应输出:1 1 3 ;
直接用序列推出括号序列,再计算w序列。(大暴力)
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int a[100000],ans[100000];
char kuo[100000];
int main()
{
    //freopen("t2.in","r",stdin);
    //freopen("t2.out","w",stdout);
    int n,i,j;
    scanf("%d",&n);
    while(n--)
    {
        int m,v=0;
        scanf("%d",&m);
        memset(a,0,sizeof(a));
        memset(ans,0,sizeof(ans));
        memset(kuo,0,sizeof(kuo));
        for(i=1;i<=m;i++)
        {
            scanf("%d",&a[i]);
            int s=a[i]-a[i-1];
            int k;
            for(k=1;k<=s;k++)
            {
                kuo[v+k]=‘(‘;
            }
            v+=s;
            v++;
            kuo[v]=‘)‘;
        }
        int h=1;
        for(i=1;i<=v;i++)
        {
            if(kuo[i]==‘)‘)
            {
                int ans1=0,y=1;
                for(j=i-1;j>=1;j--)
                {
                    if(kuo[j]==‘)‘)
                    {
                        y++;
                    }
                    if(y>0&&kuo[j]==‘(‘)
                    {
                        y--;
                        ans1++;
                    }
                    if(y==0)
                    {
                        break;
                    }
                }
                ans[h]=ans1;
                h++;
            }
        }
        printf("%d",ans[1]);
        for(i=2;i<=m;i++)
        {
            printf(" %d",ans[i]);
        }
        printf("\n");
    }
    //system("pause");
    return  0;
}

  

poj 1068