? ?利用棧可以巧妙的解決該問(wèn)題。

? ?之所以可以用棧可以解決，關(guān)鍵在于想通就算是第1個(gè)和第N個(gè)是配對(duì)，一直刪除配對(duì)下去，也是會(huì)在隊(duì)列的中間就有個(gè)配對(duì)的，所以棧的使用并不會(huì)和排隊(duì)排成圈這一特性有沖突。應(yīng)該想通即使出現(xiàn)第1個(gè)和第N個(gè)配對(duì)這樣的特例，也是可以從中間向兩邊散開(kāi)消除，到最后棧還是會(huì)出現(xiàn)空的情況。

? ?一開(kāi)始忘了STL里面有棧，使用數(shù)組去模擬棧（數(shù)組模擬棧的要點(diǎn)在于存儲(chǔ)棧頂所在的索引位置）。如下：

// 雖然可以用下面的方法模擬棧，但很明顯不如直接用stack<int> #include <iostream> using namespace std; int main() {int a[200001], b[200000], N, m, w;cin >> N;while ( N != 0) {int i;for ( i = 0; i < N; i++ ) {cin >> m >> w;a[m] = w;a[w] = m;}int pointer = 0;b[0] = 1;for ( i = 1; i <= 2*N; i++ ) {if(pointer == -1) {b[0] = a[i];}else {if( a[i] == b[pointer] ) {pointer--;}else {pointer++;b[pointer] = i;}}}if(pointer == 0)cout << "Yes\n";elsecout << "No\n";cin >> N;} }

? ?看了習(xí)題講解的PPT后發(fā)現(xiàn)有現(xiàn)成的STL可以用，所以果斷換了STL，也順利通過(guò)：

#include <iostream> #include<stack> using namespace std; int main() {int a[200001], b[200000], N, m, w;cin >> N;while ( N != 0) {int i;for ( i = 0; i < N; i++ ) {cin >> m >> w;a[m] = w;a[w] = m;}stack<int> s;for (int i=1;i<=2*N;i++) {if (!s.empty()&&s.top()==a[i])s.pop();elses.push(i);}if(s.empty())cout << "Yes\n";elsecout << "No\n";cin >> N;} }

轉(zhuǎn)載于:https://blog.51cto.com/xuewei/1348504

總結(jié)

以上是生活随笔為你收集整理的sicily 1021. Couples 栈的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。