UVa 11111 Generalized Matrioshkas

嵌套玩具, 要求外层玩具的尺寸比内层玩具尺寸的和要大. 每一个玩具由一个负数与相应的正数表示, 在这两数之间的部分即为此玩具内部的玩具. 要求判断一串输出的数字是否能组成一个合法的玩具. 一个合法的玩具:
1. 数字代表了 toy 的尺寸大小.
2. 外层的 size 必须 > 内层 size 的和, 不能是 >=.
3. 每次必须是负正对一起出现.

思路：

用一个结构体代表玩具，成员变量为容量和内部和（即嵌套在内部的元素和）

负数：

如果压栈元素大于外层容量，失败
计算外层的内部和，如果内部和大于容量，也失败
否则可以压栈

正数：

出栈并判断是否匹配

最后，如果栈为空，则成功

#include<cstdio>

#include<cstring>

#include<iostream>

#include<string>

#include<stack>

#include<algorithm>

#include<sstream>

using namespace std;

struct toy

{

        toy(int value, int inner_sum):v(value), sum(inner_sum) {}

        //容量

        int v;

        //内部和

        int sum;

};

bool solve(string & line)

{

        //cout<<line<<endl;

        istringstream iss(line);

        int x;

        stack<toy> st;

        while(iss>>x)

        {

                //小于0压栈

                if(x<0)

                {

                        x=abs(x);

                        //非最外层

                        if(!st.empty())

                        {

                                //内层大于外层

                                if(st.top().v<x)

                                        return false;

                                //统计内层的元素和,如果大于等于外层容量，返回失败

                                st.top().sum+=x;

                                if(st.top().sum>=st.top().v)

                                        return false;

                        }

                        st.push(toy(x, 0));

                }

                //大于0弹栈，并判断是否匹配

                else

                {

                        if(st.empty())

                                return false;

                        int y=st.top().v; st.pop();

                        if(x!=y)

                                return false;

                }

        }

        return st.empty();

}

int main()

{

        string line;

        while(getline(cin, line))

        {

                if(solve(line))

                        cout<<":-) Matrioshka!"<<endl;

                else

                        cout<<":-( Try again."<<endl;

        }

    return 0;

}

巴特西

UVa 11111 Generalized Matrioshkas

最新文章

热门文章