Description

 这天小g遇到了一个队列，小g觉得队列乱糟糟的不好看。于是小g希望将队列调整成为一个等差数列(差可为0)。但是小g对每个数都最多调整一次，每次可以对这个数加一、减一。请你帮助小g解决这个问题，如果能调整出等差队列，输出需要调整的数的最小数量，否则输出-1。

 

Input

第一行一个整数n(2 <= n <= 100000)，表示数列中数的个数；

第二行为n个整数pi (1 <= pi <= 1e9)。

Output

输出一个整数，表示操作数量的最小值。如果不存在则输出-1。

Sample Input

4
24 21 14 10
2
500 500
3
14 5 1
5
1 3 6 9 12

Sample Output

3
0
-1
1

HINT

 

 第一个队列调整成[25,20,15,10]花费三次操作

C++版本一

题解：

问最少修改几次可以成为一个等差数列，等差数列由公差决定，因此只考虑前两项即可确定整个数列。

#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 3e5+9;
const int INF = 1e9+9;
int vec[MAX_N];
int res[MAX_N];
int N,M,T,S;
queue<int> que;

int main(){
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    while(cin>>N){
        for(int i=0;i<N;i++){
            scanf("%d",&vec[i]);
        }
        if(N==1 ||N==2){
            cout<<0<<endl;
            continue;
        }
        int ax = INF;
        for(int a=0;a<3;a++){
            for(int b =0;b<3;b++){
                int t = vec[1]+b-1 - (vec[0]+a-1);
                int pre = vec[1] + b - 1;
                bool f = true;
                int ans = abs(a-1)+abs(b-1);
                //cout<<pre<<"..."<<t<<"...."<<ans<<endl;
                for(int i=2;i<N;i++){
                    int temp = vec[i] - pre;
                    if(abs(temp - t) > 1) {
                        //cout<<vec[i]<<".!!!!..."<<pre<<endl;
                        f = false;
                        break;
                    }
                    ans += abs(pre+t-vec[i]);
                    pre = pre + t;

                }
                if(f) {
                    ax = min(ax,ans);
                }
            }
        }
        if(ax != INF)cout<<ax<<endl;
        else cout<<-1<<endl;
    }

}

C++版本二

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <string.h>
#include <cmath>
#include <queue>
using namespace std;
typedef long long ll;
const int N=100000+100;
int t,n,m,ans;
int a[N];
void bfs(int k,int c,int d){
    if(k>=n+1){
        if(ans==-1)
            ans=c;
        else
            ans=min(ans,c);
        return;
    }
    for(int i=-1;i<=1;i++){
        if((a[k]+i)-a[k-1]==d){
            a[k]+=i;
            if(i==0)
                bfs(k+1,c,d);
            else
                bfs(k+1,c+1,d);
            a[k]-=i;
        }
    }
}
 
int main()
{
    while(scanf("%d",&n)!=EOF){
        for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
        ans=-1;
        for(int i=-1;i<=1;i++){
                a[1]+=i;
            for(int j=-1;j<=1;j++){
                a[2]+=j;
                bfs(3,abs(i)+abs(j),a[2]-a[1]);
                a[2]-=j;
            }
                a[1]-=i;
        }
        cout << ans << endl;
    }
    //cout << "Hello world!" << endl;
    return 0;
}