数组 \(a = [a_1, a_2, \cdots, a_n]\) 被称为是美丽的，如果可以将 \([1, x]\) 段移到 \([x + 1, n]\) 段后面，\(x \geq 0\) ，数组可以构成非降序。
现在有一个数组 \(a\) （一开始为空）和 \(q\) 个询问，第 \(i\) 个询问给一个正整数 \(x_i\) 。需要逐步执行以下操作。
- 若 \(x_i\) 拼接到 \(a\) 末尾，可以使得 \(a\) 为美丽的，则拼接。并输出 \(1\) 。
- 否则输出 \(0\) 。
显然是个涉及到细节的分类讨论题，两种思路。
思路一。不难观察到 \(a\) 要么是一段非降序。要么是两端非降序，假设断点在 \(x(a_x < a_{x - 1})\) 。需要满足 \(\forall i \in [2, x - 1], a_i \geq a_{i - 1}\) ， \(\forall i \in [x + 1, n]， a_i \geq a_{i - 1}, max_{i = x}^{n} a_i \leq a_1\) 。
于是有如下的模拟算法：
设输入数组 \(b\) ，指针 \(i\) 从 \(1\) 到 \(n\) ，维护 \(a\) 的末尾值 \(last\) ，且显然 \(b_1 = a_1\) 。
- 断点未出现：
若 \(i = 1\) 或者 \(b_i \geq last\) ，则 \(last = b_i\) ，输出 \(1\) 。否则，定义断点出现，若 \(b_i \leq b_1\) ，\(last = b_i\) 。输出 \(0\) 。 - 断点出现：
若 \(b_i \geq last\) 并且 \(b_i \leq b_1\) ，\(last = b_i\) ，输出 \(1\) 。否则，输出 \(0\) 。
view
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
void solve(){
int n; std::cin >> n;
std::vector<int> a(n+1);
for (int i = 1; i <= n; i++) std::cin >> a[i];
int brk_p = 0, last = 0;
for (int i = 1; i <= n; i++) {
if (brk_p == 0) {
if (i == 1 || a[i] >= last) {
last = a[i];
std::cout << 1;
}
else if (a[i] <= a[1]) {
last = a[i];
std::cout << 1;
brk_p = i;
}
else {
std::cout << 0;
}
}
else if (brk_p != 0) {
if (a[i] >= last && a[i] <= a[1]) {
last = a[i];
std::cout << 1;
}
else {
std::cout << 0;
}
}
}
std::cout << '\n';
}
int main() {
int _ = 1; std::cin >> _;
while (_--) solve();
return 0;
}
第二种思路。不妨真的维护一个数组 \(a\) 。且可以把他视为一个循环移位的数组，即 \(1, n\) 相邻。
- 若 \(a\) 满足 \(\forall i \in [2, n], a_i \geq a_{i - 1}\) 。则显然 \(a\) 是美丽的。
- 若 \(a\) 中存在一个 \(j\) 使 \(a_j > a_{j + 1}\) 。让循环数组 \(a\) 选择在 \(j + 1\) 断开，于是只需 \(a_{1} \geq a_{j + 1}\) 即可。
- 若 \(a\) 中存在两个或以上 \(j\) 使 \(a_j > a_{j + 1}\) ，无论选择哪个位置断开 \(a\) ，总会存在至少一个 \(a_x > a_{x + 1}\) 的位置。
view
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
void solve(){
int n; std::cin >> n;
std::vector<int> a;
int bad = 0;
for (int i = 1; i <= n; i++) {
int x; std::cin >> x;
if (a.empty()) {
a.push_back(x);
std::cout << 1;
}
else {
int nxt_bad = bad + (x < a.back());
if (nxt_bad == 0 || (nxt_bad == 1 && x <= a[0])) {
a.push_back(x);
bad = nxt_bad;
std::cout << 1;
}
else {
std::cout << 0;
}
}
}
std::cout << '\n';
}
int main() {
int _ = 1; std::cin >> _;
while (_--) solve();
return 0;
}