poj 1068 模拟题

本是古典何须时尚 2022-03-29 06:07 175阅读 0赞

呵呵，自己去思考的就是不一样啊！！加油！孩子~

/*
     * =====================================================================================
     *
     *       Filename:  main.cpp
     *
     *    Description:  poj 1068 模拟题
     *           我是用数组存储括号，左括号标记为0，右括号标记为1；然后再用一个
     *           bool型used[]数组标记该括号是否已经匹配过。
     *           每次输入一个数的时候都可以得到一个匹配，然后从这个括号向前匹配
     *           找到第一个没有匹配过的左括号，就可以得到结果。
     *           其中还要注意的是每次输入的时候，要判断是哪一位标记成右括号。
     *
     *        Version:  1.0
     *        Created:  2012/5/6 23:51:58
     *       Revision:  none
     *       Compiler:  gcc
     *
     *         Author:  Jason Damon 
     *   Organization:  XD Uninversity
     *
     * =====================================================================================
     */
    #include <stdlib.h>
    #include <iostream>
    #include <fstream>
    
    using namespace std;
    #define MAX 10000
    bool used[MAX];
    int a[MAX];
    int t,n;
    
    int main()
    {
        int i,j,tem,sum,pre,after;
        freopen("in.txt","r",stdin);
        scanf("%d",&t);
        while(t--)
        {
            memset(a,0,sizeof(a));
            memset(used,false,sizeof(used));
            scanf("%d",&n);
            for(i=0; i<n; i++)
            {
                if(i==0)  //第一次匹配
                {
                    scanf("%d",&pre);
                    tem=pre;
                }
                else
                {
                    scanf("%d",&after);
                    tem=after-pre+1+tem;  //做个转换，得出本次右括号的位置
                    pre=after;
                }
                a[tem]=1;
                sum=0;
                for(j=tem-1; j>=0; j--)
                {
                    if(used[j]==false && a[j]==0)  //左括号并且没有匹配
                    {
                        sum++;
                        used[j]=true;
                        if(i==0)
                        {
                            printf("%d",sum);
                            break;
                        }
                        else
                        {
                            printf(" %d",sum);
                            break;
                        }
                    }
                    else if(a[j]==0 && used[j]==true)  //左括号，但是已经匹配了
                    {
                        sum++;
                    }
                }
            }
            printf("\n");
        }
        return 0;
    }