【牛客编程巅峰赛S1第8场】牛牛构造等差数列

题目

给定 n 个数，对每个数可以进行 +1 或 -1 操作，但对于每一个数，该操作最多只能执行一次。
目标是：使用最少的操作次数，将这几个数构造成一个等差数列。
如果完全不能构造成功，就输出 -1。

解题思路

枚举序列 b 中前 2 个数的操作，每个数有 3 种操作（+1，-1，+0），所以共有 9 种情况。
每种情况确定了一个等差数列，因为等差数列的首元素 a1 和公差 d 已确定。判断后面的数是否符合这个等差数列。

C++代码

class Solution {
public:
    /**
     * 返回最少多少次操作后能使这几个数变成一个等差数列，如果完全不能构造成功，就返回-1
     * @param n int整型 代表一共有n个数字
     * @param b int整型vector 代表这n个数字的大小
     * @return int整型
     */
    int solve(int n, vector<int>& b) {
        // write code here
        if(n <= 2)
            return 0;
        int ans = -1;
        for(int i=-1; i<=1; ++i){
            for(int j=-1; j<=1; ++j){
                int tmp = 0;
                if(i) ++tmp;
                if(j) ++tmp;
                int a1 = b[0] + i;
                int a2 = b[1] + j;
                int d = a2 - a1;
                int pre = a2;
                bool flag = true;
                for(int k=2; k<n; ++k){
                    if(b[k] - pre == d){
                        pre = b[k];
                    }
                    else if(b[k] - pre == d - 1){
                        ++tmp;
                        pre = b[k] + 1;
                    }
                    else if(b[k] - pre == d + 1){
                        ++tmp;
                        pre = b[k] - 1;
                    }
                    else{
                        flag = false;
                        break;
                    }
                }
                if(flag){
                    if(ans == -1)
                        ans = tmp;
                    else
                        ans = min(ans, tmp);
                }
            }
        }
        return ans;
    }
};