Time Limit: 1 second Memory Limit: 50 MB
【問題描述】
Tom最近在研究一個有趣的排序問題。如圖所示，通過2個棧S1和S2，Tom希望借助以下4種操作實現將輸入序列升序排序。操作a如果輸入序列不為空，將第一個元素壓入棧S1操作b如果棧S1不為空，將S1棧頂元素彈出至輸出序列操作c如果輸入序列不為空，將第一個元素壓入棧S2操作d如果棧S2不為空，將S2棧頂元素彈出至輸出序列如果一個1~n的排列P可以通過一系列操作使得輸出序列為1，2，…，(n-1)，n，Tom就稱P是一個“可雙棧排序排列”。例如(1,3,2,4)就是一個“可雙棧排序序列”，而(2,3,4,1)不是。下圖描述了一個將(1,3,2,4)排序的操作序列：當然，這樣的操作序列有可能有幾個，對于上例(1,3,2,4)，是另外一個可行的操作序列。Tom希望知道其中字典序最小的操作序列是什么。【輸入】
共2行。第一行是一個整數n。第二行有n個用空格隔開的正整數，構成一個1~n的排列。【輸出】
共一行，如果輸入的排列不是“可雙棧排序排列”，輸出數字0；否則輸出字典序最小的操作序列，每兩個操作之間用空格隔開，行尾沒有空格。【輸入樣例1】
41 3 2 4【輸出樣例1】
a b a a b b a b【輸入樣例2】
42 3 4 1【輸出樣例2】
0【輸入樣例3】
32 3 1【輸出樣例3】
a c a b b d【 限制】
30%的數據滿足： n<=1050%的數據滿足： n<=50100%的數據滿足： n<=1000【題目鏈接】:http://noi.qz5z.com/viewtask.asp?id=b804
【題意】 給你兩個棧; 讓你利用這兩個棧,將所給無序排列順序輸出;
【題解】 什么時候要用到兩個棧呢? 可以用1 2 3來理解; 1 2 3則只要一個棧就夠了,每次進去之后直接輸出 1 3 2第一個進去直接出來,第2個，第3個都壓進同一個棧里面,然后按照棧規則順序彈出 2 1 3第一個和第二個都壓進去然后順序彈出,然后再把3壓進去再彈出 2 3 1可以嘗試一下,怎么搞都沒辦法用一個棧實現; 3 1 2和3 2 1都能用一個棧搞; 所以只有 2 3 1這種情況不能用一個棧搞; 但是如果2和3放在兩個棧里面就能搞了; 根據這個規則即 如果i< j< k 且存在a[k]< a[i]< a[j]; 則i和j要放在不同棧里面; 其他情況都能用一個棧搞定; 寫個二分圖染色; 如果可以染色就表示可以; 不能染色直接輸出0; 優先把數字染色為1,其次染色為2; 然后對于顏色為1的,進第一個棧,顏色為2的進第二個棧; 每次看看該進相應棧的棧頂元素是不是比當前元素大,如果是就進棧; 否則出棧就好; 模擬一下就好; 【完整代碼】
#include <cstdio>#include <algorithm>#include <cmath>#include <stack>#include <string>using namespace std;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define LL long long#define rep1(i,a,b) for (int i = a;i <= b;i++)#define rep2(i,a,b) for (int i = a;i >= b;i--)#define mp make_pair#define pb push_back#define fi first#define se second#define rei(x) scanf("%d",&x)#define rel(x) scanf("%I64d",&x)typedef pair<int,int> pii;typedef pair<LL,LL> pll;const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};const double pi = acos(-1.0);const int MAXN = 1e3+100;struct abc{ int en,nex,w;};abc bian[MAXN*MAXN*2];int n,a[MAXN],mi[MAXN],tot,fir[MAXN],col[MAXN];string ans = "";stack <int> sta[3];void add(int x,int y){ bian[++tot].nex = fir[x]; fir[x] = tot; bian[tot].en = y;}void dfs(int x,int c){ if (!col[x]) col[x] = c; else if (col[x]!=c) { puts("0"); exit(0); } else return; for (int i = fir[x];i;i = bian[i].nex) dfs(bian[i].en,3-c);}int main(){ //freopen("F://rush.txt","r",stdin); rei(n); rep1(i,1,n) rei(a[i]); mi[n]=a[n]; rep2(i,n-1,1) mi[i] = min(mi[i+1],a[i]); rep1(i,1,n-2) rep1(j,i+1,n-1) if (mi[j+1]<a[i] && a[i]<a[j]) add(i,j),add(j,i); rep1(i,1,n) if (!col[i]) dfs(i,1); int sr = 1,sc = 1; while (true) { if (sc>n) break; if (col[sr] == 1 && (sta[1].empty()||sta[1].top()>a[sr])) { sta[1].push(a[sr]); sr++; ans+='a'; continue; } if (!sta[1].empty() && sta[1].top()==sc) { sta[1].pop(); ans+='b'; sc++; continue; } if (col[sr] == 2 && (sta[2].empty()||sta[2].top()>a[sr])) { sta[2].push(a[sr]); sr++; ans+='c'; continue; } if (!sta[2].empty() && sta[2].top()==sc) { sta[2].pop(); ans+='d'; sc++; continue; } } int len = ans.size(); rep1(i,0,len-1) { putchar(ans[i]); if (i==len-1) puts(""); else putchar(' '); } return 0;}新聞熱點
疑難解答
