https://codeforces.com/contest/2060/problem/D
题目大意
给出 $n \ (2 \le n \le 2 \times 10^5)$ 长的数组 $a$ 其中 $1 \le a_i \le 10^9$。问数组是否可以靠以下操作完成排序。
任选 $i \in [1, n - 1]$，$a_i, a_{i + 1}$ 都减去 $\min(a_i, a_{i + 1})$。
简要题解
这题分不高大概是结论很好猜，但其实并不是很好证明。
观察：
- 一个位置重复多次操作没有意义 $a_i$ 或者 $a_{i + 1}$ 变为 $0$ 之后之后就只能减掉 $0$ 了。
- 如果一个位置变为 $0$ 了，则其左侧的所有位置都需要变为 $0$。
- 对于已经有序的数组我们从 $1 \sim n - 1$ 顺着执行一遍操作它还是有序的（因为会依次把左边小的置为 $0$）。
结论：我们只要顺序执行 $1, 2, 3, \cdots n - 1$ 即可。
由于观察 1 我们知道最终的额操作序列，没必要有重复的操作。
对于不重复的操作，假设其最大操作对应为 $i = m$。此操作会将 $a_m$ 或 $a_{m + 1}$ 置为 $0$，则由观察 $2$ 我们知道最终的形式为 $[1, m]$ 都为 $0$，后面的元素都有序。
现在证明，总可以贪心的将 $i = 1$ 的操作拿到开始。
- $a_1 = 0$ 是平凡的，$i = 1$ 发生在任何时候都不生效，因此我们可以将其放于开始（虽然题目原始数据没有这种情况，但因为我们将要递归的证明，因此这件事是需要的）。
- 如果序列里 $i = 1$ 的操作出现的比 $i = 2$ 的操作更早，由于 $i = 1$ 的操作只改变 $a_1, a_2$ 因此无论 $i = 1$ 的位置在哪，都可以保证 $i = 2$ 的操作进行时，$a_2$ 的值是一样的，于是我们可以将 $i = 1$ 放于开始。
- 如果序列里 $i = 1$ 晚于 $i = 2$，由于最终 $a_1 = a_2 = 0$，则执行 $a_1$ 时必有 $a_1 = a'_2$，又由于 $i = 1$ 和 $i = 2$ 是唯二能改变 $a_2$ 值的方式，则我们知道执行 $i = 2$ 时有 $a_2 = a_1 + a'_3$，且执行完后 $a_3$ 为 $0$。同样的我们将 $i = 1$ 的操作移动到开头，则执行 $i = 2$ 时有 $a''_2 = a'_3$ 即我们没有改变 $a_2$ 执行之后 $[2, n]$ 其他元素的结果，而其他操作也与 $a_1$ 的值无关。
从而问题规约为，判断是否执行了 $i = 1$ 之后的数组还是可以被操作排序的。递归证明即可。
至此我们可以将所有小于 $m$ 操作都按顺序排放了。对于所有大于 $m$ 的，由观察 $3$，我们可以直接将这些操作加到尾部。
复杂度
$T$：$O(n)$
$S$：$O(n)$
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
void solve() {
int n; cin >> n;
vector<int> a(n);
for (int& i : a) cin >> i;
for (int i = 1; i < n; i++) {
int diff = min(a[i - 1], a[i]);
a[i - 1] -= diff;
a[i] -= diff;
}
for (int i = 1; i < n; i++) {
if (a[i - 1] > a[i]) {
cout << "NO\n";
return;
}
}
cout << "YES\n";
}
int main() {
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
Next: [CF] D. Turtle Tenacity: Continual Mods - Codeforces Round 929 (Div. 3)