盘子序列

模拟 栈

题面

有$n$个盘子。盘子被生产出来后,被按照某种顺序摞在一起。初始盘堆中如
果一个盘子比所有它上面的盘子都大,那么它是安全的,否则它是危险的。称初
始盘堆为$A$,另外有一个开始为空的盘堆$B$。为了掩盖失误,生产商会对盘子序
列做一些“处理”,每次进行以下操作中的一个:

• 将$A$最上面的盘子放到$B$最上面;
• 将$B$最上面的盘子给你。

在得到所有$n$个盘子之后,你需要判断初始盘堆里是否有危险的盘子。

• $n\leq10^5$

解析

$考场80pts算法$

如果初始盘堆真的合法，会怎么样？
最后出来的序列，肯定是一个倒序结构，如$\{5,4,3,2,1\}$之类。
或者说，如果在把$\{3,2,1\}$弄到$B$盘后，先取出$\{3,2\}$,最后会形成$\{3,2,5,4,1\}$。
即你每取出一段时，这一段肯定是倒序的。
如果不是倒序，则开始了新的一段。
在初始盘堆中，新的一段在先前一段的下面或者还可以跨过了先前一段向上。
则新一段数中，

• 最小值应大于前一段的最大值或小于前一段最小值(坠坠坠坠坠重要的是，还要判断该段是否与前一段最小值相接）
• 最大值应大于前一段最大值**

然后我因考场上没想清楚，漏了第一点。。。
注意防止自己设的变量初始值成为有效限制条件（如$mn$)
此想法已弃坑，因难以保证正确性

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=2e5+100;
int n,a[N],mx,mn,lasmx;
int main()
{
  freopen("disk.in","r",stdin);
  freopen("disk.out","w",stdout);
  while(scanf("%d",&n)!=EOF)
    {
      re int flag=1;
      fp(i,1,n) a[i]=gi();mx=a[1];mn=1e9;
      fp(i,2,n)
    {
      if(!flag) break;
      if(a[i]>a[i-1])
        {
          if(a[i-1]<lasmx&&a[i-1]>mn) flag=0;
          else mn=a[i-1];
          if(a[i]<mx) flag=0;
          else lasmx=mx,mx=a[i];
        }
    }
      puts(flag?"Y":"J");
    }
  fclose(stdin);
  fclose(stdout);
  return 0;
}

$100pts算法$

据说这是一道栈的入门题？？？WC
先开一个合法初始队列栈$A$。
看你现在要弹出哪个数，若比$B$栈顶数大就把$A$栈的数弹进来，若比$B$栈顶数小就弹$B$数直到找到那个数为止。然后弹出那个数即可。
弹不出就不合法。

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=2e5+100;
int n,a[N],b[N],sta[N],stb[N],topa,topb,mx,mn,lasmx;
il ll gi() 
{
  re ll x=0,t=1;
  re char ch=getchar();
  while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
il void wri(re int x)
{
  if(x<0) putchar('-'),x=-x;
  if(x>9) wri(x/10);
  putchar(x%10+'0');
}
int main()
{
  freopen("a.in","r",stdin);
  freopen("a.out","w",stdout);
  while(scanf("%d",&n)!=EOF)
    {
      re int len,flag=1;
      fp(i,1,n) a[i]=b[i]=gi();
      sort(b+1,b+1+n);
      len=unique(b+1,b+1+n)-b-1;
      fp(i,1,n) a[i]=lower_bound(b+1,b+1+len,a[i])-b;
      fp(i,1,n) sta[i]=n-i+1;topa=n;topb=0;
      fp(i,1,n)
    {
      while(stb[topb]<a[i]&&topa) stb[++topb]=sta[topa--];
      while(stb[topb]>a[i]&&topb) --topb;
      if(stb[topb]^a[i]||!topb) {flag=0;break;}else --topb;
    }
      puts(flag?"Y":"J");
    }
  fclose(stdin);
  fclose(stdout);
  return 0;
}