PAT1051：给定stack的容量，给定数据的入栈顺序：从1开始的正整数序列，在允许随机的出栈操作的情况下，要求判断某出栈序列是否可能。
比如，告知stack容量为5，入栈序列的最大值为7。有两个序列需要判断合理性：
1 2 3 4 5 6 7： 这个序列是可能的，只需每次入栈时都做出栈操作。3 2 1 7 5 6 4： 这个序列是不可能的，其中前半部分3 2 1是合法的，先将1 2 3顺序入栈，然后三次执行出栈操作。而之后的7 5 6则是不可能的。
先讲讲自己的思路，首先栈有一个容量，那么怎么快速判断当前操作是否<=最大容量，那么我们可以将当前的值减去（下标-1），判断是否大于最大的 容量即可。。
第二个就是你会发现，如果一个大数字抛出后，后面小的元素一定是降序排列的... 那么怎么用算法实现，首先我们判断下相邻两个元素，a1 a2，如果a1>a2 我们就不考虑
如果a1<a2 ，那么我们就去前面找找看，是否有元素>a2 ，那么就可以很快想到用树状数组来维护了....
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N =1111; int bit[N],b[N],m; void add(int x) { while(x<=m) { bit[x]+=1; x+=x&-x; } } int sum(int x) { int ans=0; while(x>0) { ans+=bit[x]; x-=x&-x; } return ans; } int main() { int n,k,i,j; cin>>n>>m>>k; while(k--) { memset(bit,0,sizeof(bit)); for(i=1;i<=m;i++) cin>>b[i]; if(b[1]>n) { printf("NO\n"); continue; } add(b[1]); for(i=2;i<=m;i++) { if(b[i]-i+1>n) break; if(b[i]>b[i-1] && sum(m)-sum(b[i])>0) break; add(b[i]); } if(i>m) printf("YES\n"); else printf("NO\n"); } return 0; }
要完成判定过程，常规思路是直接使用的stack数据结构模拟出栈序列做操作，然后判定是否会触犯条件。但考虑到PAT1051中时间限制只有10ms，虽然常规方法是线性的，似乎也无法保障（事实证明是错误的，用常规方法也能在PAT上AC），我想到从序列本身的特性入手，找规律，于是有了一种效率更高的判定逻辑。
直接使用出栈序列指导stack模拟操作。判定条件有两条：
1.栈中数据量不超过栈的容量。2.出栈只能从栈顶取，不应该出现从固定的堆栈中取出其他数据的情况。算法描述如下：
用游标记录当前已知压栈的最大数据cur。如果新的读入数据tmp（即出栈序列中的某数据）大于cur，则将cur到tmp之间的数据顺序压入栈中，更新cur并执行检查1；如果新的读入数据tmp小于cur，则一定是直接出栈获得的，执行检查2。
如果能顺利完成就是合理的，如果操作过程违背了一些规则，则判定为不合理。C++实现代码如下：
#include<stdio.h> #include<stack> using namespace::std; int m, n, k, tmp, cur; bool flag; stack<int> s; int main() { scanf("%d %d %d", &m, &n, &k); while(k --) { flag = true; cur = 1; s.push(1); for (int i = 0; i != n; ++ i) { scanf("%d", &tmp); if (tmp > cur) { for (int j = cur + 1; j <= tmp; ++ j) s.push(j); if (s.size() > m) flag = false; cur = tmp; }else { if (s.top() != tmp) flag = false; } s.pop(); } if (flag) printf("YES\n"); else printf("NO\n"); } }实际上，在PAT1051的环境下，由于入栈序列数据由小到大排列非常特殊，要通过出栈序列判定可能性是存在简便思路的。
对比分析题中Sample给出的序列，结合上面提到的两条冲突条件入手分析：
1.栈中数据量不超过栈的容量：
只有在入栈时，才会需要考虑栈中数据是否超量。出栈序列中的每个数，都以为着在出栈操作之前，它刚入栈，那么当它入栈的时候能否判定是否超过栈容量呢？可以的，（当前的出栈数值 - 已经执行过的出栈操作数量）就是当前栈中元素的数量。
2.出栈只能从栈顶取，不应该出现从固定的堆栈中取出其他数据的情况。
根据观察分析发现，当某数据m出栈之后，比m小的数据如果在m之后出栈的，它们所组成的序列本身需要保持从大到小的顺序排列。距离如3 2 1 7 5 6 4这个序列，在7之后有5 6 4这个子序列，它们都大于7，但却没有保持一个递减的顺序，不合法。
C++实现代码如下：
#include<stdio.h> int m, n, k; int max, min, tmp; bool flag; int main() { scanf("%d %d %d", &m, &n, &k); while(k --) { flag = true; max = 0; min = 1001; for (int i = 0; i != n; ++ i) { scanf("%d", &tmp); if (tmp > max) { if (tmp - i > m) flag = false; else max = min= tmp; } else { if ( tmp > min) flag = false; else min = tmp; } } if (flag) printf("YES\n"); else printf("NO\n"); } }