Codeforces 1750A. Indirect Sort

A. Indirect Sort

You are given a permutation a1,a2,…,an of size n, where each integer from 1 to n appears exactly once.

You can do the following operation any number of times (possibly, zero):

Choose any three indices i,j,k (1≤i If ai>ak, replace ai with ai+aj. Otherwise, swap aj and ak.
Determine whether you can make the array a sorted in non-descending order.

Input
Each test consists of multiple test cases. The first line contains a single integer t (1≤t≤5000) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer n (3≤n≤10) — the length of the array a.

The second line contains n integers a1,a2,…,an (1≤ai≤n, ai≠aj if i≠j) — the elements of the array a.

Output
For each test case, output “Yes” (without quotes) if the array can be sorted in non-descending order, and “No” (without quotes) otherwise.

You can output “Yes” and “No” in any case (for example, strings “YES”, “yEs” and “yes” will be recognized as a positive response).

Example
inputCopy
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
outputCopy
Yes
Yes
No
No
No
No
Yes
Note
In the first test case, [1,2,3] is already sorted in non-descending order.

In the second test case, we can choose i=1,j=2,k=3. Since a1≤a3, swap a2 and a3, the array then becomes [1,2,3], which is sorted in non-descending order.

In the seventh test case, we can do the following operations successively:

Choose i=5,j=6,k=7. Since a5≤a7, swap a6 and a7, the array then becomes [1,2,6,7,4,5,3].
Choose i=5,j=6,k=7. Since a5>a7, replace a5 with a5+a6=9, the array then becomes [1,2,6,7,9,5,3].
Choose i=2,j=5,k=7. Since a2≤a7, swap a5 and a7, the array then becomes [1,2,6,7,3,5,9].
Choose i=2,j=4,k=6. Since a2≤a6, swap a4 and a6, the array then becomes [1,2,6,5,3,7,9].
Choose i=1,j=3,k=5. Since a1≤a5, swap a3 and a5, the array then becomes [1,2,3,5,6,7,9], which is sorted in non-descending order.
In the third, the fourth, the fifth and the sixth test cases, it can be shown that the array cannot be sorted in non-descending order.
由题意易知，当数组第一个数为1即可满足，无需理会后续操作

#include
using namespace std;
const int N = 12;
void solve() {
	int n;
	cin >> n;
	int a[N];
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	if (a[0]==1) {
		cout << "YES" << endl;
	}
	else {
		cout << "NO" << endl;
	}
}
int main(void) {
	int t; 
	cin >> t;
	while (t--) {
		solve();
	}
}
//code by 01100_10111;
//code by yxisme;
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