ACM-ICPC-OJ训练营

问题 A: 间接排序

时间限制: 1 Sec 内存限制: 128 MB
提交: 0 解决: 33
[提交][状态][讨论版][命题人:]

题目描述

给你一个大小为n的排列组合a1,a2,...,an，其中1到n的每个整数正好出现一次。
你可以做如下操作，次数不限（可能是零）：
选择任意三个下标i,j,k（1≤i<j<k≤n）。
如果a_i>a_k，用a_i+aj替换a_i。否则，交换a_j和a_k
判断你是否能使数组a以非降序排序。

每个测试由多个测试案例组成。第一行包含一个整数t（1≤t≤5000）--测试案例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数n（3≤n≤10）--数组a的长度。

第二行包含n个整数a1,a2,...,an（1≤ai≤n, i！=j时a[i]!=a[j]）

对于每个测试案例，如果数组能以非降序排序，则输出 "YES"（不带引号），否则输出 "NO"（不带引号）。

7
3
1 2 3
3
1 3 2
7
5 3 4 7 6 2 1
7
7 6 5 4 3 2 1
5
2 1 4 5 3
5
2 1 3 4 5
7
1 2 6 7 4 3 5

YES
YES
NO
NO
NO
NO
YES

ACM算法攻关部