CF Round 481 (Div. 3)--D. Almost Arithmetic Progression(思维)

Polycarp likes arithmetic progressions. A sequence [a1,a2,…,an] is called an arithmetic progression if for each i (1≤i

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 
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;
}