题意:牛牛和牛妹在玩一个游戏,在他们面前有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; }