题目内容

小红认为一个长度为$n$的数组$a$是好的，当且仅当对于任意的i均满足:

$|a_i-i|$均相等，其中数组下标$i$从$1$开始，小红每次可以对一个数加$1$或者减$1$，求把给定的数组变成好数组的最少操作次数

解题思路

给定长度为 $n$ 的数组 $a$，定义“好数组”为存在非负整数 $k$，使得对任意下标 $i$（从 1 开始）都有

我们可以通过每次对某个元素加或减 1 来调整数组，使其变为“好数组”，求最少操作次数。

1. 令 $b_i = a_i - i$，则对固定的 $k$，位置 $i$ 最终要满足
   $|a_i - i| = k$$\iff a_i = i + k\quad\text{或}$$\quad a_i = i - k.$ 注意这里并不要求最终的值必须在 $[1,n]$ 范围内，只要操作次数最少即可。

2. 对每个 $k$（$0 \le k \le n-1$）进行枚举：