152. 盘子序列

桃扇骨 2021-11-26 07:36 173阅读 0赞

## 【题目描述】： ##

有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