简答题
偏难
#13203
出栈序列的合法性 给定一个最大容量为 m 的堆栈,将 n 个数字按 1, 2, 3, ..., n 的顺序入栈,允许按任何顺序出栈,则哪些数字序列是不可能得到的…
出栈序列的合法性
给定一个最大容量为 m 的堆栈,将 n 个数字按 1, 2, 3, ..., n 的顺序入栈,允许按任何顺序出栈,则哪些数字序列是不可能得到的?例如给定 m=5、n=7,则我们有可能得到{ 1, 2, 3, 4, 5, 6, 7 },但不可能得到{ 3, 2, 1, 7, 5, 6, 4 }。
时间限制:1000
内存限制:65536
输入
输入第一行给出 3 个不超过 1000 的正整数:m(堆栈最大容量)、n(入栈元素个数)、k(待检查的出栈序列个数)。最后 k 行,每行给出 n 个数字的出栈序列。所有同行数字以空格间隔。
输出
对每一行出栈序列,如果其的确是有可能得到的合法序列,就在一行中输出 `YES`,否则输出 `NO`。
样例输入
5 7 5 1 2 3 4 5 6 7 3 2 1 7 5 6 4 7 6 5 4 3 2 1 5 6 4 3 7 2 1 1 7 6 5 4 3 2
样例输出
YES NO NO YES NO
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">//参考程序1
#include<bits/stdc++.h>
using namespace std;
int m,n,k;
bool is_possible(int out[])
{
stack<int> s;
int x=1,y=0;
next:
if(y==n)return 1;
while(1)
{
if(s.size()>=m||x>n)return 0;
s.push(x);
x++;
if(s.top()==out[y])break;
}
while(1)
{
if(s.size()==0)break;
if(s.top()==out[y])
{
s.pop();
y++;
}
else break;
}
goto next;
}
int main()
{
cin>>m>>n>>k;
for(int i=0;i<k;i++)
{
int out[n];
for(int j=0;j<n;j++)
cin>>out[j];
if(!is_possible(out))cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}
return 0;
}</pre><pre class="brush:cpp;toolbar:false">//参考程序2
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int main() {
int m, n, k;
cin >> m >> n >> k;
while (k--) {
vector<int> seq(n);
for (int i = 0; i < n; ++i) {
cin >> seq[i];
}
stack<int> st;
int current_max = 0;
bool valid = true;
for (int v : seq) {
if (v > current_max) {
int needed = v - current_max;
if (st.size() + needed > m) {
valid = false;
break;
}
for (int i = current_max + 1; i <= v; ++i) {
st.push(i);
}
current_max = v;
st.pop(); // 弹出v
} else {
if (st.empty() || st.top() != v) {
valid = false;
break;
} else {
st.pop();
}
}
}
cout << (valid ? "YES" : "NO") << endl;
}
return 0;
}</pre><p></p>
这道题暂未补解析。