Ian and Array Sorting
题面翻译
题目描述
为了感谢 \(\textrm{lan}\)，\(\textrm{Mary}\) 赠送了 \(\textrm{lan}\) 一个长度为 \(n\) 的序列。为了让他自己看起来聪明，他想要让序列按非递减排序。他可以执行以下操作若干次：
-
选择数组中的两个元素 \(a_i,a_{i+1}\) ( \(1\le i<n\) )。
-
同时将它们减去 \(1\)，或者都加上 \(1\)。
（注意：操作后 \(a_i,a_{i+1}\) 可以是负数或 \(0\)）
作为一个聪明人，你会注意到，有些序列 \(\textrm{lan}\) 无法让其非递减排序。因此，你决定编写一个程序来确定是否可以使数组按非递减顺序排列。
输入格式
第一行是一个正整数 \(t\) ( \(1\le t\le 10^4\) )，表示测试数据的数量。
对于每组数据：
第一行是一个正整数 \(n\) ( \(1\le n\le 3\cdot 10^5\) )，表示序列中有多少元素。
第二行是 \(n\) 个正整数 \(a_1,a_2,\dots,a_n\) ( \(1\le a_i\le 10^9\) )，表示序列 \(a\) 的元素。
保证 \(n\) 的总和不超过 \(3\cdot 10^5\)。
输出格式
对于每个测试数据，如果该序列在操作后能按非递减顺序排序，输出 YES，否则输出 NO。
你可以打印 YES，yEs，yes，Yes，这些都是可以被接受的。
题目描述
To thank Ian, Mary gifted an array $ a $ of length $ n $ to Ian. To make himself look smart, he wants to make the array in non-decreasing order by doing the following finitely many times: he chooses two adjacent elements $ a_i $ and $ a_{i+1} $ ( $ 1\le i\le n-1 $ ), and increases both of them by $ 1 $ or decreases both of them by $ 1 $ . Note that, the elements of the array can become negative.
As a smart person, you notice that, there are some arrays such that Ian cannot make it become non-decreasing order! Therefore, you decide to write a program to determine if it is possible to make the array in non-decreasing order.
输入格式
The first line contains a single integer $ t $ ( $ 1 \leq t \leq 10^4 $ ) — the number of test cases. The description of test cases follows.
The first line of each test case consists of a single integer $ n $ ( $ 2\le n\le 3\cdot10^5 $ ) — the number of elements in the array.
The second line of each test case contains $ n $ integers $ a_1,a_2,\ldots,a_n $ ( $ 1\le a_i\le 10^9 $ ) — the elements of the array $ a $ .
It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 3\cdot10^5 $ .
输出格式
For each test case, output "YES" if there exists a sequence of operations which make the array non-decreasing, else output "NO".
You may print each letter in any case (for example, "YES", "Yes", "yes", "yEs" will all be recognized as positive answer).
样例 #1
样例输入 #1
5
3
1 3 2
2
2 1
4
1 3 5 7
4
2 1 4 3
5
5 4 3 2 1
样例输出 #1
YES
NO
YES
NO
YES
分析
如果一个序列满足非递减, 即 a1 <= a2 <= a3 <= ... <= an, 那么我们一定可以通过操作使得 a1 = a2 = a3 =...<= an, 那我们就看看能不能操作原序列让它变成这样
枚举2到n-1, 我们通过操作 a[i] 和 a[i + 1] 让 a[i] = a[i - 1], 就这样一路传递下去, 看看最后
a[n - 1] <= a[n] 是否成立
如果不成立, 但是序列长度为奇数, 我们可以通过对(1, 2), (3, 4) .... 进行减1操作, 最终还是能构成一个非递减序列, 而我们也肯定可以把前 n - 1 个数变成相等的, 让差值由最后一个数来承担, 所以当长度为奇数时, 直接输出 YES 即可
如果不成立, 且序列长度为偶数, 那我们就没办法通过上述操作构造非递减序列, 输出 NO
注意: 差值可能会滚雪球越滚越大, 不仅差值要用 long long 存, 序列里的数也要
代码
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 3e5 + 10;
ll a[N];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t; cin >> t;
while (t--)
{
int n; cin >> n;
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
if (n % 2)
{
printf(" YES\n");
continue;
}
for (int i = 1; i < n - 1; i++)
{
ll v = a[i] - a[i - 1];
a[i] -= v;
a[i + 1] -= v;
}
if (a[n - 2] <= a[n - 1])
printf(" YES\n");
else
printf(" NO\n");
}
}