Codeforces1401 C. Mere Array

本文主要是介绍Codeforces1401 C. Mere Array，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

You are given an array 𝑎1,𝑎2,…,𝑎𝑛 where all 𝑎𝑖 are integers and greater than 0.

In one operation, you can choose two different indices 𝑖 and 𝑗 (1≤𝑖,𝑗≤𝑛). If 𝑔𝑐𝑑(𝑎𝑖,𝑎𝑗) is equal to the minimum element of the whole array 𝑎, you can swap 𝑎𝑖 and 𝑎𝑗. 𝑔𝑐𝑑(𝑥,𝑦) denotes the greatest common divisor (GCD) of integers 𝑥 and 𝑦.

Now you’d like to make 𝑎 non-decreasing using the operation any number of times (possibly zero). Determine if you can do this.

An array 𝑎 is non-decreasing if and only if 𝑎1≤𝑎2≤…≤𝑎𝑛.

Input
The first line contains one integer 𝑡 (1≤𝑡≤104) — the number of test cases.

The first line of each test case contains one integer 𝑛 (1≤𝑛≤105) — the length of array 𝑎.

The second line of each test case contains 𝑛 positive integers 𝑎1,𝑎2,…𝑎𝑛 (1≤𝑎𝑖≤109) — the array itself.

It is guaranteed that the sum of 𝑛 over all test cases doesn’t exceed 105.

Output
For each test case, output “YES” if it is possible to make the array 𝑎 non-decreasing using the described operation, or “NO” if it is impossible to do so.

Example
inputCopy
4
1
8
6
4 3 6 6 2 9
4
4 5 6 7
5
7 5 2 2 4
outputCopy
YES
YES
YES
NO
Note
In the first and third sample, the array is already non-decreasing.

In the second sample, we can swap 𝑎1 and 𝑎3 first, and swap 𝑎1 and 𝑎5 second to make the array non-decreasing.

In the forth sample, we cannot the array non-decreasing using the operation.

题意：
可以选定两个gcd为最小数的数交换。求能否使得a数组不降。

思路：
假设最小数为mi，那么求出所有因数存在mi的数，这些数就可以任意换位置（用mi来操作）。
所以将因数存在mi的数排序，再看序列是否不减就好了。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>using namespace std;typedef long long ll;const int maxn = 1e5 + 7;int a[maxn];int main() {int T;scanf("%d",&T);while(T--) {int n;scanf("%d",&n);int mi = 1e9;for(int i = 1;i <= n;i++) {scanf("%d",&a[i]);mi = min(mi,a[i]);}vector<int>vec;for(int i = 1;i <= n;i++) {if(a[i] % mi == 0) {vec.push_back(a[i]);}}sort(vec.begin(),vec.end());int cnt = 0;for(int i = 1;i <= n;i++) {if(a[i] % mi == 0) {a[i] = vec[cnt++];}}int flag = 1;for(int i = 2;i <= n;i++) {if(a[i] < a[i - 1]) {flag = 0;}}if(!flag) {printf("NO\n");} else {printf("YES\n");}}return 0;
}

这篇关于Codeforces1401 C. Mere Array的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---