题意为将所给序列通过一种交换操作变为递增序列,交换规则为:若选中的两个元素的最大公约数为所给序列的最小值则可以交换位置。正面去想肯定会有很多的可变因素,所以直接反着来,先将序列排序,对比前后序列相同位置的每个数,因为是排序后,已满足gcd要求,所以只要满足原序列的与排序后序列相同位置的不同元素是最小值的倍数即可。
#include<bits/stdc++.h> using namespace std; int main() { int t,n,p,a[100005]={0},b[100005]={0}; bool f1=true;//标记无法交换的情况 cin>>t; while(t--) { cin>>n; for(int i=0;i<n;i++) { cin>>a[i]; b[i]=a[i]; } sort(a,a+n);//懒人必备(其他的感觉会炸) p=a[0]; for(int i=0;i<n;i++) { if(a[i]!=b[i]&&b[i]%p) { cout<<"NO"<<endl; f1=false; break; } } if(f1) cout<<"YES"<<endl; f1=true; } return 0; }