本文主要是介绍poj 2090 Two-Stacks Solitaire，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这道题不是特别简单，我自己考虑了很久，未果。于是希望在网络上找到参考，但是网上参考不多
题意：给一个数列，两个栈，要求数列从后往前依次入栈，问能否使出栈序列是不减的。（双栈排序）
分析：利用二分图染色法。
首先观察那些牌绝对不能压入同一个栈，若两个不能入同一栈则连一条边，然后根据二分图染色，看是否能构成二分图。如果不能直接输出impossible
两张牌i,j不能入同一栈的充要条件是，i>j>k（i最先入栈） && a[k]<a[i]<a[j]
然后根据每个点所染的颜色决定把每个牌压入哪个栈。然后模拟即可。
原代码：
//用图论的思想来做题
//二分图着色#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>using namespace std;#define maxn 250struct
{int v,next;
}edge[maxn*maxn];int n;
int stock[maxn], f[maxn];
int head[maxn], ecount, color[maxn], q[maxn];
int out[maxn];
bool ok;
int stk1[maxn], stk2[maxn];
int top1, top2, step;inline int min(int a,int b){ return a<b?a:b; }void input()
{for (int i =0; i < n; i++){scanf("%d", &stock[i]);out[i] = stock[i];}
}void addedge(int&a, int&b)
{edge[ecount].next = head[a];edge[ecount].v = b;head[a] = ecount++;
}void bfs(int&s)
{int front =0;int rear =1;q[0] = s;color[s] =1;while (front != rear){int a = q[front++];for (int i = head[a]; i !=-1; i = edge[i].next){int b = edge[i].v;if (!color[b]){q[rear++] = b;color[b] =3- color[a];}else if (color[a] == color[b]){ok =false;return;}}}
}void make(int i)
{int a = stock[i];bool did =true;while (did){did =false;if (top1 >0&& stk1[top1 -1] ==out[step]){top1--;printf("pop 1\n");step++;did =true;}if (top2 >0&& stk2[top2 -1] ==out[step]){top2--;printf("pop 2\n");step++;did =true;}}if (i <0)return;if (color[i] ==1){stk1[top1++] = a;printf("push 1\n");}else{stk2[top2++] = a;printf("push 2\n");}
}void print()
{top1 = top2 =0;step =0;for (int i = n -1; i >=0; i--)make(i);make(-1);
}void work()
{memset(head, -1, sizeof(head));f[0] = stock[0];int i;for (i =1; i < n; i++)f[i] = min(f[i -1], stock[i]);ecount =0;for (i =1; i < n -1; i++){for (int j = i +1; j < n; j++){if (stock[j] >= stock[i])continue;if (stock[j] > f[i -1]){addedge(i, j);addedge(j, i);}}}ok =true;memset(color, 0, sizeof(color));for (i =0; i < n; i++){if (!color[i])bfs(i);if (!ok){printf("impossible\n");return;}}print();
}int main()
{//freopen("t.txt", "r", stdin);int t =0;while (scanf("%d", &n), n){t++;printf("#%d\n", t);input();sort(out, out+ n);work();}return 0;
}不知道哪里出错的代码。。：
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>#define MAXN 250
using namespace std;struct
{int v,next;
}edge[MAXN*MAXN]; //待连线的边//输入的原数组是a[]，排序后数组是b[]
int a[MAXN],b[MAXN];
int N; // 1 <= N <= 208
int f[MAXN]; //存放前i个输入中的最小值，判断能不能在一个栈中使用
int head[MAXN], ecount, color[MAXN], q[MAXN];
bool ok;
int stk1[MAXN], stk2[MAXN];
int top1, top2, step;inline int min(int a,int b){ return a<b?a:b; }//addedge
void addedge(int&a, int&b)
{//其实用一个二维数组会更容易edge[ecount].next = head[a];edge[ecount].v = b;head[a] = ecount++;
}//bfs
void bfs(int&s)
{int front =0;int rear =1;q[0] = s;color[s] =1;while (front != rear){int d = q[front++];for (int i = head[d]; i !=-1; i = edge[i].next){int c = edge[i].v;if (!color[c]){q[rear++] = c;color[c] =3- color[d];}else if (color[d] == color[c]){ok =false;return;}}}
}//make
void make(int i)
{int temp = a[i];bool did =true;while (did){did =false;if (top1 >0&& stk1[top1 -1] ==b[step]){top1--;printf("pop 1\n");step++;did =true;}if (top2 >0&& stk2[top2 -1] ==b[step]){top2--;printf("pop 2\n");step++;did =true;}}if (i <0)return;if (color[i] ==1){stk1[top1++] = temp;printf("push 1\n");}else{stk2[top2++] = temp;printf("push 2\n");}
}//print
void print()
{top1 = top2 =0;step =0;for (int i = N-1; i >=0; i--)make(i);make(-1);
}//work
void work()
{memset(head, -1, sizeof(head));f[0]=a[0];int i;//f[i]中存的相当于是前i次中最小的数for (i =1; i < N; i++)f[i] = min(f[i -1], a[i]);//连边ecount =0; //边数for (i =1; i < N -1; i++){for (int j = i +1; j < N; j++){if (a[j] >= a[i])continue;//如果上一个 if 中a[j]<a[i]，这里又大于前[i-1]个输入中的最小值//证明有[i-1]中的某个k，j>i>k时，有a[k]<a[j]<a[i]//入栈顺序是j,i,kif (a[j] > f[i -1]){addedge(i, j);addedge(j, i);}}}ok=true;memset(color, 0, sizeof(color));for (i =0; i < N; i++){if (!color[i])bfs(i);if (!ok){printf("impossible\n");return;}}print();
}int main()
{int i;int t=0;while(~scanf("%d",&N) && N!=0){for(i=0;i<N;i++){scanf("%d",&a[i]);b[i]=a[i];}printf("#%d\n", ++t);//排序b[]sort(b,b+N);work();}return 0;
}
这篇关于poj 2090 Two-Stacks Solitaire的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
