codeforces|Codeforces Round #665 (Div. 2) C. Mere Array codeforces|算法

Title
CodeForces 1401 C. Mere Array
Time Limit
2 seconds
Memory Limit
256 megabytes
Problem Description
You are given an arraya 1 , a 2 , … , a n a_1, a_2, \dots, a_n a1?,a2?,…,an? where alla i a_i ai? are integers and greater than0 0 0.
In one operation, you can choose two different indicesi i i andj j j ( 1 ≤ i , j ≤ n 1 \le i, j \le n 1≤i,j≤n). Ifg c d ( a i , a j ) gcd(a_i, a_j) gcd(ai?,aj?) is equal to the minimum element of the whole arraya a a, you can swapa i a_i ai? anda j a_j aj?.g c d ( x , y ) gcd(x, y) gcd(x,y) denotes the greatest common divisor (GCD) of integersx x x andy y y.
Now you’d like to makea a a non-decreasing using the operation any number of times (possibly zero). Determine if you can do this.
An arraya a a is non-decreasing if and only ifa 1 ≤ a 2 ≤ … ≤ a n a_1 \le a_2 \le \ldots \le a_n a1?≤a2?≤…≤an?.
Input
The first line contains one integert t t ( 1 ≤ t ≤ 1 0 4 1 \le t \le 10^4 1≤t≤104) — the number of test cases.
The first line of each test case contains one integern n n ( 1 ≤ n ≤ 1 0 5 1 \le n \le 10^5 1≤n≤105) — the length of arraya a a.
The second line of each test case containsn n n positive integersa 1 , a 2 , … a n a_1, a_2, \ldots a_n a1?,a2?,…an? ( 1 ≤ a i ≤ 1 0 9 1 \le a_i \le 10^9 1≤ai?≤109) — the array itself.
It is guaranteed that the sum ofn n n over all test cases doesn’t exceed1 0 5 10^5 105.
Output
For each test case, output “YES” if it is possible to make the arraya a a non-decreasing using the described operation, or “NO” if it is impossible to do so.
Sample Input

4 1 8 6 4 3 6 6 2 9 4 4 5 6 7 5 7 5 2 2 4

Sample Onput

YES YES YES NO

Note
In the first and third sample, the array is already non-decreasing.
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.
Source
CodeForces 1401 C. Mere Array
题意给出一个序列 a a a
设序列最小值为 m i n i mini mini
你只能交换 g c d ( a i , a j ) = = m i n i gcd(a_i,a_j)==mini gcd(ai?,aj?)==mini的两个数
求是否可能使得序列非递减排序。
思路直接模拟
拿出最小值，所以是最小值的倍数的元素之间都可以任意交换(通过mini)。
【codeforces|Codeforces Round #665 (Div. 2) C. Mere Array】则将那些元素排序后放回原数组，查看是否有序即可
AC代码:

#include using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; const int maxn = 3e5 + 5; const ll inf = 0x3f3f3f3f; const ll mod = 1e9 + 7; #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend()int main() { ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); int T; cin >> T; while (T--) { int n; cin >> n; vector a(n); for (auto &it : a) cin >> it; int mini = *min_element(all(a)); vector b; for (auto &it : a) { if (it % mini == 0) b.emplace_back(it); } sort(all(b)); for (int i = 0, now = 0; i < n; ++i) { if (a[i] % mini == 0) a[i] = b[now++]; } cout << (is_sorted(all(a)) ? "YES" : "NO") << endl; } return 0; }