题目描述
有 n 个盘子. 盘子被生产出来后, 被按照某种顺序摞在一起. 初始盘堆中如果一 个盘子比所有它上面的盘子都大, 那么它是安全的, 否则它是危险的. 称初始盘堆为 A, 另外有一个开始为空的盘堆 B. 为了掩盖失误, 生产商会对盘子序列做一些 “处理”, 每次进行以下操作中的一个:
- 将 A 最上面的盘子放到 B 最上面;
- 将 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;
}