首页 › 题库 › C/C++编程考级 › C/C++编程六级 › 简答题
简答题 偏难
#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&lt;bits/stdc++.h&gt; using namespace std; int m,n,k; bool is_possible(int out[]) { stack&lt;int&gt; s; int x=1,y=0; next: if(y==n)return 1; while(1) { if(s.size()&gt;=m||x&gt;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&gt;&gt;m&gt;&gt;n&gt;&gt;k; for(int i=0;i&lt;k;i++) { int out[n]; for(int j=0;j&lt;n;j++) cin&gt;&gt;out[j]; if(!is_possible(out))cout&lt;&lt;"NO"&lt;&lt;endl; else cout&lt;&lt;"YES"&lt;&lt;endl; } return 0; }</pre><pre class="brush:cpp;toolbar:false">//参考程序2 #include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;stack&gt; using namespace std; int main() { int m, n, k; cin &gt;&gt; m &gt;&gt; n &gt;&gt; k; while (k--) { vector&lt;int&gt; seq(n); for (int i = 0; i &lt; n; ++i) { cin &gt;&gt; seq[i]; } stack&lt;int&gt; st; int current_max = 0; bool valid = true; for (int v : seq) { if (v &gt; current_max) { int needed = v - current_max; if (st.size() + needed &gt; m) { valid = false; break; } for (int i = current_max + 1; i &lt;= 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 &lt;&lt; (valid ? "YES" : "NO") &lt;&lt; endl; } return 0; }</pre><p></p>
这道题暂未补解析。