题目描述:
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≤i≤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≤t≤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≤n≤3⋅10^5)\) — the number of elements in the array.
The second line of each test case contains \(n\) integers \(a_1,a_2,…,a_n(1≤ai≤10^9)\) — the elements of the array \(a\).
It is guaranteed that the sum of \(n\)over all test cases does not exceed \(3⋅10^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).
样例：
input:
5
3
1 3 2
2
2 1
4
1 3 5 7
4
2 1 4 3
5
5 4 3 2 1
output:
YES
NO
YES
NO
YES
AC代码：
思路:
这个题直接写没有思路，但是可以转换成\(a_2-a-1,a_3-a_2...a_n-a_{n-1}\)
设这个数组为\(b_1,b_2,...b_{n-1}\)
\(a_1,a_2...a_n\)是一个非递减序列当且仅当\(b\)数组为非负数
最后可以看到有两种改变的情况
-
\(i\)在\(1\)~\(n-3\)时，\(b_i\) 加或减 \(1\)，则 \(b_i + 2\) 减或加\(1\)
-
单独改变\(b_2\)和\(b_{n-2}\)且不影响其他数
所以在\(n\)为奇数时，\(n-2\)为奇数。所以对于\(b_{n-2}\)我们可以给它加上足够大的数
所以\(i\)为奇数时，我们可以任意改变其他\(i\)为奇数的\(b\)的值使得它们为非负数
而\(i\)为偶数时同理，给\(b_2\)加上足够大的数，使得其他\(i\)为偶数的\(b\)的值为非负数
当\(n\)为偶数时，\(n-2\)为偶数，我们给\(b_2\)和\(b_{n-2}\)加上足够大的数，此时只能保证\(i\)为偶数时\(b\)的值都为非负数
\(i\)为奇数的\(b\)的值，我们可以随意分配，但是\(b\)的值的总和都是不变的
所以此时只要将\(i\)为奇数时的b的总和加起来，其值大于等于\(0\)则代表可以保证\(b\)的值为非负数
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
void solve()
{
int n;
cin >> n;
vector<int> a(n + 1);
for(int i = 1; i <= n; i ++)
cin >> a[i];
if(n % 2 == 1)
{
cout << "YES\n";
return;
}
LL sum = 0;
for(int i = 2; i <= n; i += 2)
sum += a[i] - a[i - 1];
if(sum >= 0)
{
cout << "YES\n";
return;
}
cout << "NO\n";
}
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int T;
cin >> T;
while(T --)
solve();
return 0;
}