题目描述

有 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 \leq 8\)

80% 的数据保证 \(n \leq 1000\)

100% 的数据保证 \(1 \leq n \leq 100000\),\(0 \lt Plate\ size \lt 1000000000\) 且互不相等

Explanation

维护一个栈. 我们先从正面考虑问题: 将 A 中的元素不停向 B 中 push, 然后再随机 pop and push 一些元素到栈 C 中. 如此一来就可以得到栈 C.

反过来从栈 C 推回到栈 A. C push 回栈 B 的过程中, 若要 B 推回栈 A 的元素满足题设的连续单调性, 则必须要求 B 中的元素也连续. 所以我们在从 C 推入 B 的过程中应该检验 单调性, 最后在全部推入 A 时检验全部的单调性.

另外此题数据极水, 这个做法可以 AC (雾)

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <stack>

using namespace std;
typedef long long lli;
const int maxn = 100100;

int T, n;
int arr[maxn];

int rarr[maxn], rarridx; // Resultint array
bool judge(void)
{
    stack<int> stk;
    rarridx = 0;
    for (int i = n; i >= 1; i--) {
        // The element to be pushed.
        int push = arr[i];
        // Pushing top sequence to stack. If the stack is empty or the stack
        // top is greater than the current to be pushed, then the top must
        // be eradicated from the stack. Then the eradicated is to be saved
        // into the results' array.
        while (!stk.empty() && stk.top() >= push) {
            int save = stk.top();
            stk.pop();
            rarr[++rarridx] = save;
        }
        // Now pushing current value to stack.
        stk.push(push);
    }
    // Pushing unsaved changes
    while (!stk.empty()) {
        int save = stk.top();
        stk.pop();
        rarr[++rarridx] = save;
    }
    // Checking results intactness.
    for (int i = 1; i <= n - 1; i++)
        if (rarr[i + 1] >= rarr[i])
            return false;
    return true;
}

int main(int argc, char** argv)
{
    // scanf("%d", &T);
    // T = 1;
    for (int idx = 1; idx >= 1; idx++) {
        if (scanf("%d", &n) == EOF)
            break;
        for (int i = 1; i <= n; i++)
            scanf("%d", &arr[i]);
        bool res = judge();
        printf("%s\n", res ? "Y" : "J");
    }
    return 0;
}