UVa 1111 Generalized Matrioshkas 数据结构专题

11111-Generalized Matrioshkas

2642

34.25%

742

87.60%

题目链接接：

http://uva.onlinejudge.org/index.phpoption=com_onlinejudge&Itemid=8&category=103&page=show_problem&problem=2052

题目类型： 数据结构， 链表

题目大意：

这题的题意比较难懂，看了好几变才明白。 就是有一个可以嵌套娃娃的娃娃，然后嵌套在里面的娃娃又可以继续嵌套娃娃。

然后要求直接嵌套在里面（内一层）的娃娃的尺寸大小之和不能超过外面的。 例如，-3 -2 2 3,代表有两层，-3和3表示一个嵌套（这个娃娃的尺寸大小为3，且负数一定要在左边先出现），里面时-2和2表示一个大小2的娃娃。 再比如-5 -2 2 -1 1 5,表示有3个娃娃，5嵌套这2和1。当有更多层的嵌套时，如-9 -7 -22 -3 -2 -112379，表示9嵌套着7.然后7又嵌套着2（左边的-2，2）和3， 3又嵌套这2（右边出现的-2，2）， 这个2又嵌套着1。 只要相邻的层次，内一层的大小相加起来小于（不能等于）外一层的大小就满足条件。

解题思路：

这一题也和“括号嵌套”有点像。 首先是题目的输入，由于一开始没有采用一个好的输入方案，导致WA了无数次，浪费了几个小时。 然后题目需要注意的一些地方：1.如果娃娃个数是奇数，则直接判断错误； 2. 正数个数和负数不想等，也是错误的； 3.如果

正数先于对应的负数出现，也是错误的。

我采用的方法是，开一个数组level，用来保存各个层次娃娃的容量，然后每次遇到一个‘）’时就进行处理， 把当前这个层次的”外层“容量减去这个层次的大小。 当有个层次为0或负数时，则可以判断是错误的。最需要注意的是怎样处理和判断当前层次时哪一层。

样例输入：

-9 -7 -2 2 -3 -2 -1 1 2 3 7 9
-9 -7 -2 2 -3 -1 -2 2 1 3 7 9
-9 -7 -2 2 -3 -1 -2 3 2 1 7 9
-100 -50 -6 6 50 100
-100 -50 -6 6 45 100
-10 -5 -2 2 5 -4 -3 3 4 10
-9 -5 -2 2 5 -4 -3 3 4 9

样例输出：

:-) Matrioshka!
:-( Try again.
:-( Try again.
:-) Matrioshka!
:-( Try again.
:-) Matrioshka!
:-( Try again.

#include<cstdio>
#include<iostream>
#include<cstring>
#include<stack>
#include<cmath>
using namespace std;

string str;
int level[30000], arr[30000], numDoll, cntNeg, cntPos, n; 
stack<int>st;

bool solve(){
    if(numDoll%2==1 || cntNeg!=cntPos)
        return false;
    int i,j,index=0;
    if(numDoll==2){
        if(arr[0]<0 && arr[0]+arr[1]==0)
            return true;
        return false;
    }
    
    while(!st.empty()) 
        st.pop();

    for(i=0; i<numDoll; ++i){
        if(arr[i]<0){
            st.push(arr[i]);
            level[index++] = abs(arr[i]);
        }
        else if(arr[i]>0){
            if(st.empty() || abs(st.top()) != arr[i]) 
                 return false;
             
            if(st.size()==1){
                if(level[0] <=0 )
                    return false;
                st.pop();
            }
            else{
                st.pop();
                --index;   
                level[st.size()-1] -= arr[i];
                if( level[st.size()-1] <= 0 ){
                    return false;
                }                
            }           
        }
    }
    return true;
}

void input(){
    arr[0] = n;
    while(getchar()!='\n'){
        scanf("%d",&arr[numDoll++]);
    };   
}

int main()
{
    freopen("input.txt","r",stdin);

    bool flag=true;  
    cntNeg=0, cntPos=0;
    numDoll=1;
    while(~scanf("%d", &n)){  

        input();
        
        if(solve()) 
            printf(":-) Matrioshka!\n");
        else
            printf(":-( Try again.\n");
        
        cntNeg=0; 
        cntPos=0; 
        numDoll=1;
    }            
    return 0;
}

—— 生命的意义，在于赋予它意义。

原创http://blog.csdn.net/shuangde800，By D_Double