UVa 1111 Generalized Matrioshkas 数据结构专题

UVa 1111 Generalized Matrioshkas 数据结构专题2014-10-06 csdn博客 shuangde800题目链接接：

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 -2 2 -3 -2 -1 1 2 3 7 9，表示9嵌套着7.然后7又嵌套着2（左边的-2，2）和3， 3又嵌套这2（右边出现的-2，2），这个2又嵌套着1。只要相邻的层次，内一层的大小相加起来小于（不能等于）外一层的大小就满足条件。

解题思路：

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

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

本文URL地址：http://www.bianceng.cn/Programming/sjjg/201410/45536.htm

我采用的方法是，开一个数组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（）！="
"）{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！
"）;elseprintf（":-（ Try again.
"）;cntNeg=0; cntPos=0; numDoll=1;}return 0;}