排序 sorting.cpp

【一句话题意】给一个序列问能以否以小于等于一次交换的方式完成排序。 序列长度小于1e5

【分析】第一眼感觉是暴力，果断会超时；再想这不是问序列能否通过一次交换达到目标状态吗。又因为排序后的结果可以sort暴力求出且结果一定是惟一的，所以直接比较排序前后状态就可以了。

【code】

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1e5+1000;
int n;
int a[maxn],b[maxn];
inline void read(int &x){
	x=0;char tmp=getchar();
	while(tmp<'0'||tmp>'9') tmp=getchar();
	while(tmp>='0'&&tmp<='9') x=(x<<1)+(x<<3)+tmp-'0',tmp=getchar();
}
bool cmp(const int x,const int y){
	return x<=y;
}
int main(){
	freopen("sorting.in","r",stdin);
	freopen("sorting.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++) read(a[i]);
	for(int i=1;i<=n;i++) b[i]=a[i];
	sort(b+1,b+n+1,cmp);
	int cnt1=0,cnt2=0;
	for(int i=1;i<=n;i++){
		if(a[i]>b[i]) cnt1++;
		if(a[i]<b[i]) cnt2++;
	}
	if(cnt1>1||cnt2>1) printf("NO\n");
	else printf("YES\n");
	return 0;
}