之前记得数据结构试卷上有这种题 就是判断某一出栈顺序 是不是满足以1.2。。。n为入栈顺序
a1,a2,a3..an;
对于任意相邻a[i],a[i+1] 如果a[i]>a[i+1]+1 那么它两之间的数肯定已经在前面出栈过了 不然中间的不出栈 a[i+1]不可能出来
这一个条件就可以判断了 用数状数组求下和 就行了
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
using namespace std;
#define N 100010
#define lowbit(x) x&(-x)
int f[N],a[N],re[N],n;
void add(int x)
{
while(x<=n)
{
re[x] += ;
x+=lowbit(x);
}
}
int getsum(int x)
{
int s=;
while(x)
{
s+=re[x];
x-=lowbit(x);
}
return s;
}
int main()
{
int i,k=;
scanf("%d",&n);
for(i = ; i <= n ; i++)
{
scanf("%d",&a[i]);
}
add();
for(i = ; i < n ; i++)
{
add(a[i]);
if(a[i]>a[i+]+)
{
int x = getsum(a[i])-getsum(a[i+]);
if(x!=a[i]-a[i+])
{
k = ;
break;
}
}
}
if(k)
puts("Not a proof");
else
puts("Cheater");
return ;
}