【b804】双栈排序

2019-11-09 19:51:50

字体：大中小

来源：转载

供稿：网友

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】

【输入样例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;}

上一篇：C# Queue使用

下一篇：vue项目中使用jQuery