#36651: stack練習題
土法煉鋼 即可解決
先設一個Stack
1~n 慢慢放入，如果遇到最新放進去的值剛好是input sequence指到的位置
pop() 出來
一直持續，如果最後size是零 代表成功排好
EX: 1,2,3,4,5 要排成 5,4,3,2,1
pusg(1); push(2); push(3); push(4); push(5);
while: top() == sequence[idx]
pop();
idx++;
得到5,4,3,2,1這個序列
Code:
// accepted
# include <iostream>
# include <vector>
# include <stack>
using namespace std;
int main()
{
int n;
while(cin >> n && n) // input n train
{
while(1) // test many time
{
int num;
bool flag = false;
vector<int> v;
for(int i=0;i<n;i++) // get sequence
{
cin >> num;
if (!num)
{
flag = true;
break;
}
v.push_back(num);
}
if (flag)
{
cout << endl;
break; // reinput n
}
stack<int> s;
int idx = 0;
for(int i=0;i<n;i++)
{
s.push(i+1);
// stack 有東西 and 照著順序放出
while (s.size() && s.top() == v[idx])
{
s.pop();
idx++;
}
}
if (s.size() == 0)
cout << "Yes" <<endl;
else
cout << "No" << endl;
}
}
return 0;
}
ZeroJudge Forum