首页 > 代码库 > poj 1068

poj 1068

2024-10-03 01:37:39   214人阅读

   此题多组处理数据，每组输入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


联系
我们