T232420 购物题解

题解"/>

T232420 购物题解

原题地址：Problem - C - Codeforces

题目意思:

有n个数每次操作选择一个大于等于2的数x令这n个数等于mod x后的结果即a[i]=a[i]%x，询问是否存在一种方案使得最后n个数相等。

题目思路：

因为x大于等于2，所以原本就存在的0和1是无法改变的，如果同时存在0和1那么一定不行，如果只存在0，那么把数组排序过后从大到小依次%a[i]即可全部变为0，如果只存在1，因为1是无法操作的所有我们要把所有的数都变成1，同样的思路，将数组排序，然后依次从大到小%a[i]-1，a[i]就都变成了1，但是有一个问题就是如果数组中有一个和a[i]-1相等的数，那么当你操作a[i]时，这个数就会变成0，然后就再也无法达到题目要求了，所以当数组中有1的时候整个数组将不可以存在连续的数例如 1 3 4 这样的数组就不可以达到要求了。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod=1e9+7;
const int MAXN=1e6+7;
int a[MAXN];
int main(){int t;cin>>t;while(t--){int n,flag=0;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];if(a[i]==1){flag=1;}}if(flag==0){cout<<"YES"<<endl;}else {int f=1;sort(a+1,a+n+1);for(int i=1;i<n;i++){if(a[i]==a[i+1]-1){f=0;break;}}if(f) cout<<"YES"<<endl;else cout<<"NO"<<endl;}}system("pause");return 0;
}