算法并不難，是需要用到棧就行了，一個元素記錄兩個值：自身的大小和剩余的容量。
當(dāng)遇到一個負(fù)數(shù)的時候，如果當(dāng)前棧頂元素可以容納，直接壓入棧中，否則則失敗；
當(dāng)遇到一個正數(shù)的時候，和棧頂元素比較，相加為0的話，彈出棧頂元素，同時修改當(dāng)前棧頂元素的剩余容量，相加不為0，則失敗。
注意：最終如果成功的話，棧應(yīng)該為空。
以下是我的代碼：
#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 閱讀(718)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：數(shù)據(jù)結(jié)構(gòu)