首页 > 试题广场 >

牛牛构造等差数列

[编程题]牛牛构造等差数列
  • 热度指数:333 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
牛牛和牛妹在玩一个游戏,在他们面前有n个数,他们对每个数可以进行 +1 或 -1 操作,但对于每一个数,该操作最多只能执行一次。
游戏胜利的目标是:使用最少的操作次数,将这几个数构造成一个等差数列。
牛牛特别想赢得游戏,所以他想让你帮他写一个程序,得出最少多少次操作后能使这几个数变成一个等差数列,当然,如果完全不能构造成功,就输出-1。
示例1

输入

4,[24,21,14,10]

输出

3

说明

在第一个例子中,牛牛应该对第一个数字+1,对第二个数字-1,对第三个数字+1,而第四个数字应该保持不变。最后,序列就变成了[25,20,15,10],这是一个等差数列且操作次数最少。
示例2

输入

3,[14,5,1]

输出

-1

说明

在第二个例子中,不可能只对其中的数字最多操作一次就得到等差数列。

备注:




class Solution:
    def solve(self , n , b ):
        if n<=2:
            return 0
        d_set=set()
        for i in range(-1,2,1):
            for j in range(-1,2,1):
                a0= b[0] + i
                a1= b[1] + j
                d=a1-a0
                d_set.add((a0,d))#记录首项a0和公差d
        res=[]
        for a0_d in d_set:
            r=0
            a0,d=a0_d[0],a0_d[1]
            for k in range(n):
                ak=a0+k*d
                if abs(b[k] - ak)<=1:
                    r+=abs(b[k] - ak)
                else:
                    r=-1
                    break
            res.append(r)
        res_=list(filter(lambda x:x!=-1,res))
        return min(res_) if res_ else -1

发表于 2020-08-31 22:29:43 回复(0)