首页 > 代码库 > 2017 6 11模拟赛
2017 6 11模拟赛
盘子序列
【题目描述】
有 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
【数据范围】
20%的数据保证 n<=8
80%的数据保证 n<=1,000
100%的数据保证 1<=n<=100,000，0<盘子大小<1,000,000,000 且互不相等
模拟，考试的时候想着双栈排序那道题，就考虑到，当且仅当i<j<k&&a[j]<a[k]<a[i]是不能用单栈排序（i位于三者最底层），好像和这个题是同样的道理，所以就这么写出来了，没多想，考完顿悟了，这个做法复杂度O(n^2),还不如开个栈模拟
/*考完试一气之下写的这个丑代码我也不想说什么了，感觉像在乱搞*/#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>using namespace std;#define maxn 100010int n,top1,top2,top3;struct node{ int num,rank,id;}a[maxn],b[maxn];int cmp1(node x,node y){ return x.num>y.num;}int cmp2(node x,node y){ return x.id<y.id;}int main(){ freopen("disk.in","r",stdin); freopen("disk.out","w",stdout); while(scanf("%d",&n)!=EOF){ bool flag=0; memset(a,0,sizeof(a));top1=0;top2=0;top3=1; for(int i=1;i<=n;i++)scanf("%d",&a[++top1].num),a[top1].id=i; sort(a+1,a+n+1,cmp1); for(int i=1;i<=n;i++)a[i].rank=i; sort(a+1,a+n+1,cmp2); while(top1>=1){ int t1=top1,t2=top2,t3=top3; while(top2!=0&&b[top2].rank==top3){ top3++;top2--; } if(a[top1].rank==top3){ top3++;top1--; } else{ while(a[top1].rank!=top3&&b[top2].rank!=top3){ if(top1<=0){ flag=1;break; } b[++top2]=a[top1--]; } } if(t1==top1&&t2==top2&&t3==top3){ break; } if(flag==1)break; } while(top2!=0&&b[top2].rank==top3){ top3++;top2--; } if(flag==1)printf("J\n"); else if(top3!=n+1){ printf("J\n"); } else printf("Y\n"); }}
2017 6 11模拟赛
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。