题解"/>
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;
}
更多推荐
T232420 购物题解
发布评论