首页 › 题库 › C/C++编程考级 › C/C++编程六级 › 简答题
简答题 偏难
#13153

两头进一头出 某队列允许在其两端进行入队操作,但仅允许在一端进行出队操作。现给定入队的序列,请你判断一系列出队序列是否可能。 例如按 1、2、3、4、5 的顺序…

两头进一头出

某队列允许在其两端进行入队操作,但仅允许在一端进行出队操作。现给定入队的序列,请你判断一系列出队序列是否可能。

例如按 1、2、3、4、5 的顺序入队,则 1、3、2、5、4 这样的出队序列是可以得到的,但 5、1、3、2、4 就是不可能得到的。

时间限制:4000,内存限制:65536

输入

输入首先在一行中给出两个正整数 N 和 K(≤ 10),分别是入队元素的个数和待查验的序列个数。

随后一行给出 N 个两两不同的整数组成的入队序列;再跟着 K 行,每行给出由 N 个入队整数组成的出队序列。同行整数间以空格分隔。

输出

对每个需要查验的出队序列,如果是可能的,则在一行中输出 yes,否则输出 no。

样例输入

5 4
10 2 3 4 5
10 3 2 5 4
5 10 3 2 4
2 3 10 4 5
3 5 10 4 2

样例输出

yes
no
yes
no
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">//该答案由AI生成 #include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;deque&gt; #include &lt;set&gt; #include &lt;map&gt; using namespace std; bool check(vector&lt;int&gt;&amp; in, vector&lt;int&gt;&amp; out, const map&lt;int, int&gt;&amp; index_map) {     deque&lt;int&gt; deq;     set&lt;int&gt; inDeque;     int n = in.size();     int i0 = 0, j0 = 0;     while (i0 &lt; n) {         if (!deq.empty() &amp;&amp; deq.front() == out[i0]) {             int x = deq.front();             deq.pop_front();             inDeque.erase(x);             i0++;         } else {             if (inDeque.find(out[i0]) != inDeque.end()) {                 return false;             }             if (j0 &gt;= n) {                 return false;             }             auto it = index_map.find(out[i0]);             if (it == index_map.end()) {                 return false;             }             int pos = it-&gt;second;             if (pos &lt; j0) {                 return false;             }             for (int k = j0; k &lt; pos; k++) {                 deq.push_back(in[k]);                 inDeque.insert(in[k]);             }             deq.push_front(in[pos]);             inDeque.insert(in[pos]);             j0 = pos + 1;             int x = deq.front();             deq.pop_front();             inDeque.erase(x);             i0++;         }     }     return true; } int main() {     int N, K;     cin &gt;&gt; N &gt;&gt; K;     vector&lt;int&gt; in(N);     map&lt;int, int&gt; index_map;     for (int i = 0; i &lt; N; i++) {         cin &gt;&gt; in[i];         index_map[in[i]] = i;     }     for (int i = 0; i &lt; K; i++) {         vector&lt;int&gt; out(N);         for (int j = 0; j &lt; N; j++) {             cin &gt;&gt; out[j];         }         if (check(in, out, index_map)) {             cout &lt;&lt; "yes" &lt;&lt; endl;         } else {             cout &lt;&lt; "no" &lt;&lt; endl;         }     }     return 0; }</pre>
这道题暂未补解析。