AcWing 5462. 修改数列
原题链接
中等
//根据只能+1,+0,-1,知道首尾一共有九种变化方法,根据这九种情况计算可能的等差数
//存在一种等参数后,从第二个开始遍历,遍历到第n - //1位,观察有没有需要变化>1的情况,有则out
//最后判断首尾的变化情况,如果加的不是0,则要分别加一点操作数
//输出最小的minn
#include<iostream>
#include<math.h>
using namespace std;
const int N = 100005;
#define ll long long
int n;
ll a[N],s[N];
int solve(int i,int j)
{
int a1 = a[1] + i,an = a[n] + j;
if((an - a1) % (n - 1))return -1;
return (an - a1) / (n - 1);
}
int main()
{
scanf("%d",&n);
for(int i = 1;i <= n;i++)
{
scanf("%lld",&a[i]);
s[i] = a[i];
}
if(n == 1)
{
cout << 0 << endl;
return 0;
}
bool ans;
ll num = 0,minn = n + 1;
for(int i = -1;i <= 1;i++)
{
for(int j = -1;j <= 1;j++)
{
num = 0;
int t = solve(i,j);
if(t != -1)
{
ans = true;
a[1] += i;
for(int p = 2;p < n;p++)
{
if(abs(a[p] - t - a[p - 1]) > 1)
{
//4
//24 21 14 10
ans = false;
break;
}
else if(abs(a[p] - t - a[p - 1]) != 0)
{
num++;
a[p] = a[p - 1] + t;
}
}
if(ans)
{
if(i != 0)num++;
if(j != 0)num++;
minn = min(minn,num);
}
for(int i = 1;i <= n;i++)
a[i] = s[i];
}
}
}
if(minn != n + 1)cout << minn << endl;
else cout << -1 << endl;
return 0;
}