Codeforces Round #709 (Div. 2, based on Technocup 2021 Final Round)---B. Restore Modulo(1500+等差数列贪心)

本文主要是介绍Codeforces Round #709 (Div. 2, based on Technocup 2021 Final Round)---B. Restore Modulo(1500+等差数列贪心)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述
题意：
给你一个用下面两个条件去构造的数组①a1=s%m,②ai=(ai-1+c)%m,并且m>0,s>=0,m>c>=0,求可以构造数组的情况下最大的m，m如果可以取无穷输出0，如果找不到一个这样的数组输出0。
思路：
注意条件有C<M，所以ai=(ai-1+c)%m，那么ai-1+c除m一定是0，那么他们将会是一个等差数列，所以想想无穷的情况比较好些只有两个以下和单调递增or单调递减的等差数列会是无穷的
合法的情况就是当ai>ai-1时求出C，这个C有且只有一个，并且再找ai-1>ai时，m=c+abs(a[i]-a[i-1])的值也有且只有一个m，那么当c和m出现不止一个时就是非法情况，并且保证最大的数要小于m，然后再扫一遍就行啦~

#include<bits/stdc++.h>using namespace std;#define int long longconst int maxn=1e5+2000;
int a[maxn];
signed main()
{int n,i,j,t;cin>>t;while(t--){cin>>n;for(i=0;i<n;i++){cin>>a[i];}if(n<=2){cout<<0<<endl;}else{map<int ,int >ca;int flag=0,c=0,ff=0,ok=0;for(i=1;i<n;i++){if(a[i-1]<a[i]){if(a[i]-a[i-1]>0&&flag==0)flag=1,c=a[i]-a[i-1];else if(a[i]-a[i-1]>0&&a[i]-a[i-1]!=c&&flag!=0)flag++;}ca[a[i-1]-a[i]]++;if(ca[a[i-1]-a[i]]==1) ok++;}if(ok==1){cout<<0<<endl;}else if(flag>1||c==0){cout<<-1<<endl;}else{flag=0;int ans=0,max1=0;for(i=1;i<n;i++){if(a[i]-a[i-1]<0&&flag==0)flag=1,ans=c+abs(a[i]-a[i-1]);else if(a[i]-a[i-1]<0&&flag!=0&&abs(a[i-1]-a[i])+c!=ans)flag++;max1=max({max1,a[i],a[i-1]});}if(flag>1||max1>=ans){cout<<-1<<endl;}else{flag=0;for(i=1;i<n;i++){if(a[i]!=(a[i-1]+c)%ans) flag=1;}if(flag==1) scf1else cout<<ans<<" "<<c<<endl;}}}}
}