https://codeforces.com/problemset/problem/382/C
题意:给定一个序列,问是否可以通过只插入一个数来使得整个序列成为等差数列,求出总共有多少可能的情况,并输出这些数。
思路:
模拟一下发现只有几种情况..然后要考虑各种细节。
其中一个是两个不同的差出现次数相等的时候要用大的差,同时要注意大的差能被2整除且/2后等于小的差
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<cstdio>
#include<algorithm>
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
const int maxn=1e5+1000;
typedef long long LL;
inline LL read(){LL x=0,f=1;char ch=getchar(); while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;}
LL a[maxn];
map<LL,LL>map1;
int main(void)
{
cin.tie(0);std::ios::sync_with_stdio(false);
LL n;cin>>n;
for(LL i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+1+n);
if(n==1){
cout<<"-1"<<"\n";
}
else if(n==2){
LL cnt=a[2]-a[1];
if(cnt==0){
cout<<1<<"\n";
cout<<a[2]<<"\n";
}
else if(cnt%2==0){
cout<<3<<"\n";
cout<<a[1]-cnt<<" ";
cout<<a[1]+cnt/2<<" ";
cout<<a[2]+cnt<<" ";
}
else{
cout<<2<<"\n";
cout<<a[1]-cnt<<" ";
cout<<a[2]+cnt<<" ";
}
}
else{
for(LL i=1;i<n;i++){
map1[a[i+1]-a[i]]++;
}
if(map1.size()>=3){
cout<<"0"<<"\n";
}
else if(map1.size()==2){
LL num1=0;LL num2=0;LL cnt1=0;LL cnt2=0;
for(auto i:map1){
num1=i.first;cnt1=i.second;
for(auto j:map1){
if(i.first==j.first) continue;
num2=j.first;cnt2=j.second;
}
break;
}
if(cnt1>=2&&cnt2>=2){cout<<"0"<<"\n";return 0;}
if(cnt1>=cnt2) swap(num1,num2),swap(cnt1,cnt2);
if(num1&1||num1/2!=num2){
cout<<"0"<<"\n";
}
else{
for(LL i=1;i<n;i++){
if(a[i+1]-a[i]==num1){
cout<<"1"<<"\n";
cout<<a[i]+num1/2<<"\n";
return 0;
}
}
}
}
else if(map1.size()==1){
map<LL,LL>:: iterator it;it=map1.begin();
LL cnt=(*it).first;
if(cnt==0){
cout<<1<<"\n";
cout<<a[1]<<"\n";
return 0;
}
cout<<2<<"\n";
cout<<a[1]-cnt<<" "<<a[n]+cnt<<"\n";
}
}
return 0;
}