有n 个盘子。盘子被生产出来后,被按照某种顺序摞在一起。初始盘堆中如果一个盘子比所有它上面的盘子都大,那么它是安全的,否则它是危险的。称初始盘堆为A,另外有一个开始为空的盘堆 B。为了掩盖失误,生产商会对盘子序列做一些“处理”,每次进行以下操作中的一个:(1)将A 最上面的盘子放到 B 最上面;(2)将 B 最上面的盘子给你。在得到所有n个盘子之后,你需要判断初始盘堆里是否有危险的盘子。
输入包含多组数据(不超过 10 组)
每组数据的第一行为一个整数 n
接下来n 个整数,第 i 个整数表示你收到的第 i 个盘子的大小
对于每组数据,如果存在危险的盘子,输出”J”,否则输出”Y”
3
2 1 3
3
3 1 2
Y
J
时间:1s 空间:128M
20%的数据保证 n<=8
80%的数据保证 n<=1,000
100%的数据保证 1<=n<=100,000,0<盘子大小<1,000,000,000 且互不相等
#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<cmath> #include<queue> using namespace std; int a[100001],b[100001],c[100001]; int main() { int i,ans,sum,n; while(~scanf("%d",&n)){ for(i=1; i<=n; i++) scanf("%d",&a[i]); for(i=n; i>0; i--){ if(!ans||b[ans]<a[i]){ b[++ans]=a[i]; } else{ while(ans&&b[ans]>a[i]){ c[++sum]=b[ans--]; } } } while(ans){ c[++sum]=b[ans--]; } for(ans=2; ans<=n; ans++){ if(c[ans]>c[ans-1]){ break; } } if(ans>n){ printf("Y\n"); } else{ printf("J\n"); } ans=sum=0; memset(b,0,sizeof(b)); memset(c,0,sizeof(c)); } return 0; }
原文:https://www.cnblogs.com/xiongchongwen/p/11192383.html