这道题不是特别简单,我自己考虑了很久,未果。于是希望在网络上找到参考,但是网上参考不多
题意:给一个数列,两个栈,要求数列从后往前依次入栈,问能否使出栈序列是不减的。(双栈排序)
分析:利用二分图染色法。
首先观察那些牌绝对不能压入同一个栈,若两个不能入同一栈则连一条边,然后根据二分图染色,看是否能构成二分图。如果不能直接输出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 250 struct { 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,k if (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; }