原题链接： https://codeforces.com/contest/1401/problem/C
文章图片
测试样例：
input样例解释：
4
1
8
6
4 3 6 6 2 9
4
4 5 6 7
5
7 5 2 2 4
output
YES
YES
YES
NO
In the first and third sample, the array is already non-decreasing.题意： 给你一个整数序列 a a a，其中你可以选择下标为 i i i和 j j j，如果 g c d ( a [ i ] , a [ j ] ) gcd(a[i],a[j]) gcd(a[i],a[j])的值为整数序列中数值最小的元素，那么就可以交换 a [ i ] a[i] a[i]和 a [ j ] a[j] a[j]。问你能否经过若干次这样的操作使得整数序列 a a a变为非递减序列。
In the second sample, we can swapa 1 a_1 a1? anda 3 a_3 a3? first, and swapa 1 a_1 a1? anda 5 a_5 a5? second to make the array non-decreasing.
In the forth sample, we cannot the array non-decreasing using the operation.
【#|C. Mere Array（排序+思维） Codeforces Round #665 (Div. 2)】解题思路： 我们的最终目的就是要将整数序列 a a a变为非递减序列。那么我们拿这个最终序列和原序列进行对比，位置上数值不对的自然是需要靠交换来改变的。而交换的条件则是上述，那么我们如果每一个需要交换的数它们的因子都包含这个最小的数，那么我们就可以通过用这个最小的数来进行交换而不用考虑其他的。假设最小的数为 m i n n minn minn，即如果我们要交换的数 x x x满足 x % m = 0 x\%m=0 x%m=0，那么我们就是可以通过这个最小的数作为媒介来进行转移，如果不行，说明这个要交换的数不能被转移，则说明不行。OK，我们具体看代码。
AC代码：
/*
*邮箱：unique_powerhouse@qq.com
*blog:https://me.csdn.net/hzf0701
*注：文章若有任何问题请私信我或评论区留言，谢谢支持。
*
*/
#include //POJ不支持#define rep(i,a,n) for (int i=a;
i<=n;
i++)//i为循环变量，a为初始值，n为界限值，递增
#define per(i,a,n) for (int i=a;
i>=n;
i--)//i为循环变量， a为初始值，n为界限值，递减。
#define pb push_back
#define IOS ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0)
#define fi first
#define se second
#define mp make_pairusing namespace std;
const int inf = 0x3f3f3f3f;
//无穷大
const int maxn = 1e5;
//最大值。
typedef long long ll;
typedef long double ld;
typedef pairpll;
typedef pair pii;
//*******************************分割线，以上为自定义代码模板***************************************//int t,n,a[maxn],b[maxn];
int main(){
//freopen("in.txt", "r", stdin);
//提交的时候要注释掉
IOS;
while(cin>>t){
while(t--){
cin>>n;
rep(i,0,n-1){
cin>>a[i];
b[i]=a[i];
}
sort(b,b+n);
//开始对比。
int minn=b[0];
int flag=false;
rep(i,0,n-1){
if(a[i]!=b[i]&&a[i]%minn!=0){
flag=true;
break;
}
}
if(flag)
cout<<"NO"< 推荐阅读
- 数据结构和算法|LeetCode 的正确使用方式
- #|7.分布式事务管理
- 每日一题|每日一题-解码（第十一届蓝桥杯）（简单思维）
- #|算法设计与分析（Java实现）——贪心算法（集合覆盖案例）
- #|算法设计与分析（Java实现）—— 动态规划 （0-1 背包问题）
- #|阿尔法点亮LED灯(一）汇编语言
- #|Multimedia
- #|ARM裸机开发（汇编LED灯实验（I.MX6UL芯片））
- 基础课|使用深度优先搜索（DFS）、广度优先搜索（BFS）、A* 搜索算法求解 (n^2 -1) 数码难题，耗时与内存占用（时空复杂度）对比（附（(n^2 - 1) 数码问题控
- #|学习笔记 | Ch05 Pandas数据清洗 —— 缺失值、重复值、异常值