首页 > 其他 > 详细

152. 盘子序列

时间:2019-07-16 01:29:46      阅读:120      评论:0      收藏: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;
}

  

152. 盘子序列

原文:https://www.cnblogs.com/xiongchongwen/p/11192383.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!