Polycarp likes arithmetic progressions. A sequence [a1,a2,…,an] is called an arithmetic progression if for each i (1≤i<n) the value ai+1−ai+1− is the same. For example, the sequences [42], [5,5,5], [2,11,20,29] and [3,2,1,0] are arithmetic progressions, but [1,0,1], [1,3,9] and [2,3,1] are not.
It follows from the definition that any sequence of length one or two is an arithmetic progression.
Polycarp found some sequence of positive integers [b1,b2,…,bn]. He agrees to change each element by at most one. In the other words, for each element there are exactly three options: an element can be decreased by 1, an element can be increased by 1, an element can be left unchanged.
Determine a minimum possible number of elements in b which can be changed (by exactly one), so that the sequence b becomes an arithmetic progression, or report that it is impossible.
It is possible that the resulting sequence contains element equals 0.
Input
The first line contains a single integer n (1≤n≤100000) — the number of elements in b.
The second line contains a sequence b1,b2,…,bn (1≤bi≤10^9).
Output
If it is impossible to make an arithmetic progression with described operations, print -1. In the other case, print non-negative integer — the minimum number of elements to change to make the given sequence becomes an arithmetic progression. The only allowed operation is to add/to subtract one from an element (can't use operation twice to the same position).
input
4
24 21 14 10
output
3
题意：给定n个数的序列，对于每一个数，可以进行+1，-1，不动，三种操作，注意每个数只能操作一次，问最少需要操作多少次使得整个序列变成等差序列，如果无解输出-1.
解析：等差数列的特点，如果首项和公差知道，那么整个序列就都知道了，因此我们枚举前两项所有的可能，一共九种，对于每种合法情况对答案取min即可。
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int a[N],b[N];
int x[9]={0,0,0,1,1,1,-1,-1,-1};
int y[9]={1,0,-1,1,0,-1,1,0,-1};
void solve()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
if(n<=2)//特判一下
{
printf("0\n");
return;
}
int ans=1e9;//设立答案
for(int i=0;i<9;i++)
{
for(int j=1;j<=n;j++) b[j]=a[j];//每种初始拷贝
b[1]+=x[i],b[2]+=y[i];
int k=b[2]-b[1],cnt=0;//cnt记录当前情况所需操作次数
if(x[i]!=0) cnt++;//此处就要累加cnt
if(y[i]!=0) cnt++;
bool ok=true;//此情况是否合法
for(int j=3;j<=n;j++)
{
int c=b[j]-b[j-1]-k;//与前一个差值的差
if(c==0) continue;
else if(c==1) b[j]--,cnt++;
else if(c==-1) b[j]++,cnt++;
else//无解情况
{
ok=false;
break;
}
}
if(ok) ans=min(ans,cnt);
}
if(ans==1e9) ans=-1;
printf("%d\n",ans);
}
int main()
{
int t=1;
//scanf("%d",&t);
while(t--) solve();
return 0;
}
