A. Ian and Array Sorting

思路:首先我们可以从前往后做一遍,把除了最后一个元素其他所有数都变成和第一个数一样的数,然后假如前n-1个数个数为偶数,这样我们分组进行操作,一定可以把所有数变成无限小,也就是说一定会有解,也就是说n为奇数一定有解,我们考虑n为偶数的情况,n为偶数,我们从前往后做一遍,前n-1个数相同,前n-2个数一定可以变为无穷小,所以我们只需要比较最后两个数也就是n-1和n的大小即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
vector<LL>a, b;
void run()
{
a.clear();
b.clear();
int n;scanf("%d", &n);
for(int i = 0; i < n; ++ i)
{
LL x; scanf("%lld", &x);
a.push_back(x);
b.push_back(x);
}
sort(b.begin(), b.end());
bool success = true;
for(int i = 0; i < n; ++ i)
if(a[i] != b[i]) success = false;

if(success)
{
puts("YES");
return;
}
if(n & 1) puts("YES");
else
{
for(int i = 1; i + 1 < n; ++ i)
{
LL d = a[i - 1] - a[i];
a[i] += d;
a[i + 1] += d;
}
if(a[n - 2] <= a[n - 1]) puts("YES");
else puts("NO");
}
}

int main()
{
// freopen("1.in", "r", stdin);
int t;cin >> t;
while(t --) run();
return 0;
}