AcWing 5462. 修改数列
原题链接
中等
作者:
周祖浩
,
2024-01-28 15:10:28
,
所有人可见
,
阅读 47
唉,迟来的题解,这题怎么说呢。。。说难也不难,说简单也不简单,还是有蛮多细节的
(但是我看别人的代码都很简单。。。。悲)
我认为这道题有几个关键点需要注意:
1、原数列无法构成等差数列的条件(最大差值-最小差值的差<=4)
2、遍历所有可能公差,通过公差确定等差数列
唉,当时写的时候脑子一下没转过来,这么简单的题目现在才解决。。。
详细看代码:
###################################
#include<bits/stdc++.h>
using namespace std;
int n;
const int maxn=1e5+5;
const int INF=1e9+5;
int a[maxn];//原数列
int d[maxn];//差值数列
int flag1;//用来判断原数列是否为等差数列
int Maxval,Minval;//表示差值的最大值和最小值,用来枚举所有可能的公差
int ad[maxn];//等差数列
int ans;//最终答案
int flag2;//每种情况是否可行
int Count;//每种情况的可能答案
void solve(){
ans=INF;
//依次枚举所有可能公差
for(int i=Minval;i<=Maxval;i++){
//当公差确定可以通过第一个数来确定整个等差数列(假设可以构成),再通过与原数列进行比较
//如果满足变换要求即可构成,否则不可构成
//枚举第一个数的三种变换情况
//注意:当一种情况可以成功构成等差数列那么他所需要修改元素个数的值是唯一的,那么最小值就要在总的所有情况中查找
//1
ad[0]=a[0]-1;
flag2=0,Count=1;
for(int j=1;j<n;j++){
ad[j]=ad[j-1]+i;
if(abs(ad[j]-a[j])>1){
flag2=1;break;
}
else if(abs(ad[j]-a[j])==1) Count++;
}
if(!flag2) ans=min(ans,Count);
//2
ad[0]=a[0];
flag2=0,Count=0;
for(int j=1;j<n;j++){
ad[j]=ad[j-1]+i;
if(abs(ad[j]-a[j])>1){
flag2=1;break;
}
else if(abs(ad[j]-a[j])==1) Count++;
}
if(!flag2) ans=min(ans,Count);
//3
ad[0]=ad[0]+1;
flag2=0,Count=1;
for(int j=1;j<n;j++){
ad[j]=ad[j-1]+i;
if(abs(ad[j]-a[j])>1){
flag2=1;break;
}
else if(abs(ad[j]-a[j])==1) Count++;
}
if(!flag2) ans=min(ans,Count);
}
//最多有4*3=12种情况
if(ans==INF) cout<<"-1";
else cout<<ans;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<n-1;i++) d[i]=a[i+1]-a[i];
//特判一开始就无法构成等差数列的情况和一开始本来就是等差数列的情况
flag1=0;
Maxval=Minval=d[0];
for(int i=0;i<n-1;i++){
Maxval=max(Maxval,d[i]);
Minval=min(Minval,d[i]);
if(i<n-2){
if(d[i]!=d[i+1]) flag1=1;
}
}
if(abs(Maxval-Minval)>4){//差值大于4无论如何使无法构成等差数列的
cout<<"-1";return 0;
}
if(!flag1){//差值全部相等,原数列就是等差数列
cout<<'0';return 0;
}
//处理一般情况
solve();
//算法复杂度为O(n)级别
return 0;
}
###################################