CF1750A Indirect Sort 题解

题目传送门

题目大意

有 \(T\) 组长度为 \(n\) 的排列；

每组进行若干次操作（每次操作选择三个数 \(i\)，\(j\)，\(k\)）：

若 \(a_i>a_k\) 将 \(a_i\) 加上 \(a_j\)，否则就交换 \(a_j,a_k\)；

问是否能使排列经过操作变成一个单调递增的序列。

解题思路

可以用一些小技巧：

由题意可知：

当 \(a_1=1\) 时，从 \(a_2\) 到 \(a_n\) 进行排序操作，最终就可以变成一个单调递增的序列。

当 \(a_1\) 不等于 \(1\) 时，它只能被增加，永远不能变成 \(1\)。

所以要满足的条件就是 \(a_1=1\)，是输出 \(Yes\)，否输出 \(No\) 即可。

代码

#include<bits/stdc++.h>
#define ri register int
using namespace std;
template <class T> void r(T&x){
	x = 0; int w = 0; char g = getchar();
	while(!isdigit(g)) {
		w = (g == '-'); g = getchar();
	} while(isdigit(g)) {
		x = (x << 3) + (x << 1) + (g xor 48); g = getchar();
	} x = w?-x:x; return;
}
int n;
int main(){
    r(n);
    while(n--){
        int x,y,s;
       	r(x),r(y);
        for(ri i=2;i<=x;i++)
			r(s);
        if(y==1)
			cout<<"Yes"<<'\n';
        else 
			cout<<"No"<<'\n';
    }
    return 0;
}

由于加了快读，代码可能显得比较冗长，但其实还是比较简单的。