算法并不难，是需要用到栈就行了，一个元素记录两个值：自身的大小和剩余的容量。
当遇到一个负数的时候，如果当前栈顶元素可以容纳，直接压入栈中，否则则失败；
当遇到一个正数的时候，和栈顶元素比较，相加为0的话，弹出栈顶元素，同时修改当前栈顶元素的剩余容量，相加不为0，则失败。
注意：最终如果成功的话，栈应该为空。
以下是我的代码：
#include<iostream>
#include<sstream>
#include<string>
#include<stack>
#include<cstdio>
using namespace std;
struct Type
{
Type(const int &a,const int &b):size_(a),capacity_(b) {}
int size_,capacity_;
};
int main()
{
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
//*/
string line;
while(getline(cin,line))
{
istringstream sin(line);
stack<Type> s;
bool success(true);
int t;
while(sin>>t)
{
if(t<0)
{
if(s.empty())
s.push(Type(t,t));
else
{
if(s.top().capacity_<t)
s.push(Type(t,t));
else
{
success=false;
break;
}
}
}
else
{
if(s.empty())
{
success=false;
break;
}
else
{
if(s.top().size_+t!=0)
{
success=false;
break;
}
else
{
s.pop();
if(!s.empty())
s.top().capacity_+=t;
}
}
}
/*
stack<Type> st(s);
while(!st.empty())
{
cout<<st.top().size_<<" "<<st.top().capacity_<<endl;
st.pop();
}
cout<<endl;
//*/
}
if(success && s.empty())
cout<<":-) Matrioshka!"<<endl;
else
cout<<":-( Try again."<<endl;
}
return 0;
}
posted on 2011-04-14 10:38
lee1r 阅读(682)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：数据结构