盘子序列

蔚落 2021-09-30 10:14 229阅读 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 且互不相等

**分析：**

本题的两种操作都对应着栈的操作，故不难想到单调栈，同时本题需要两个单调栈进行维护，从而求出最优解。

**CODE：**

1 #include<cstdio>
     2 #include<iostream>
     3 #include<cstring>
     4 #include<algorithm>
     5 using namespace std;
     6 int n;
     7 int a[100005];
     8 int s1[100005],s2[100005],t1,t2;
     9 int get(){
    10     int x=0,f=1;
    11     char ch=getchar();
    12     while(ch<'0'||ch>'9'){
    13         if(ch=='-')f=-1;
    14         ch=getchar();
    15     }
    16     while(ch>='0'&&ch<='9'){
    17         x=x*10+ch-'0';
    18         ch=getchar();
    19     }
    20     return x*f;
    21 }
    22 int main(){
    23     while(scanf("%d",&n)!=EOF){
    24         t1=t2=0;
    25         for(int i=1;i<=n;i++){
    26             a[n-i+1]=get();
    27         }
    28         for(int i=1;i<=n;i++){
    29             while(t2&&s2[t2]>a[i]){
    30                 s1[++t1]=s2[t2--];
    31             }
    32             if(!s2[t2]||a[i]>s2[t2]){
    33                 s2[++t2]=a[i];
    34             }
    35         }
    36         bool ok=true;
    37         while(t2) s1[++t1]=s2[t2--];
    38         for(int i=1;i<t1;i++){
    39             if(s1[i]<s1[i+1]){
    40                 printf("J\n");
    41                 ok=false;
    42                 break;
    43             }
    44         }
    45         if(ok){
    46             printf("Y\n");
    47         }
    48     }
    49     return 0;
    50 }

转载于:https://www.cnblogs.com/kanchuang/p/11194095.html