牛牛构造等差数列题解

题意：牛牛和牛妹在玩一个游戏，在他们面前有n个数，他们对每个数可以进行 +1 或 -1 操作，但对于每一个数，该操作最多只能执行一次。
游戏胜利的目标是：使用最少的操作次数，将这几个数构造成一个等差数列。
牛牛特别想赢得游戏，所以他想让你帮他写一个程序，得出最少多少次操作后能使这几个数变成一个等差数列，当然，如果完全不能构造成功，就输出-1。

时间复杂度: 空间复杂度:
解题思路：
贪心解法。
贪心策略：如果我们想要构造出一个等差数列，那么第二项-首项一定是等差数列的公差。那么利用这个性质，我们只需要对数列的前两项进行上述三种操作判断就好了。
注意，某些用例输出为0，比如n = 2，b=[200,200],对于n小于2时直接返回0即可。
我们可以用del = b[1] + k - b[0] + j来记录前两项的相减结果，也就是公差。
我们可以使用用now来记录a[i]得前一项。
由题目性质得：abs(b[i] - now) > 1也就是公差>1时，说明该公差不适用于整个数列；反之，因为比如第二项等于第一项的话其实就没必要操作了，所以如果now!=b[i]时，操作数+1。
由此，统计最小的操作数即可。

/**
 * 返回最少多少次操作后能使这几个数变成一个等差数列，如果完全不能构造成功，就返回-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 res = 0x3f3f3f3f;
    for (int j = -1; j <= 1; j++)
    {
        for (int k = -1; k <= 1; k++)
        {
            int del = b[1] + k - b[0] + j;
            int now = b[1] + k;
            int cnt = abs(j);
            int i;
            for (i = 1; i < n; i++)
            {
                if (abs(b[i] - now) > 1)
                    break;
                else if (b[i] != now)
                    cnt++;
                now += del;
            }
            if (i == n)
            {
                res = min(res, cnt);
            }
        }
    }
    if (res != 0x3f3f3f3f)
    {
        return res;
    }
    return -1;
}