当前位置：首页 > backend >正文

0518蚂蚁暑期实习上机考试题1：数组操作

backend 2025/7/14 11:00:48

题目

小红认为一个长度为 n 的数组 a 是好的，当且仅当对于任意的 i ，均满足 $\left | a_i-i \right |$ 相等，其中数组下标 i 从 1 开始，小红每次可以对一个数加 1 或者减 1 ，求把给定的数组变成好数组的最少操作次数。

输入描述：第一行是一个整数 $n\left ( 1\leq n\leq 1000 \right )$ ，表示数组长度。第二行是 $n$ 个整数，第 $i$ 个为 $a_i\left ( 1\leq a_i\leq n \right )$ 。

输出描述：一个整数，表示把给定的数组变成好数组的最少操作次数。

输入示例1：

3
3 2 1

输出示例1：

解释：

将数组[3,2,1]调整为[3,4,1]经过的步数最小，为2；[3,4,1]是一个好数组，满足：

输入示例2：

3
1 2 3

输出示例2：

解答

此题注意输入的第二句话：数组是 $n$ 个整数，第 $i$ 个数组元素为 $a_i\left ( 1\leq a_i\leq n \right )$ 。

$cost=\sum_{i=1}^{n}min\left ( \left | a_i-\left ( i-k \right ) \right |, \left | a_i-\left ( i+k \right ) \right |\right )$

因此，只需从0遍历k，得到最小代价时的k，然后返回这个最小代价即可。

那么 $k$ 的上界应该取多少呢？注意到：

当 $k\geq n$ 时，可以去掉绝对值：

$min\left ( \left |a_i+k-i \right |,\left |a_i-k-i \right | \right )=min\left ( a_i+k-i,k+i-a_i \right )\left ( k\geq n \right )$

注意到 $min\left ( a_i+k-i,k+i-a_i \right )$ 是一个大于等于1的数，也就是说，当 $k\geq n$ 时，对所有的 $i$ ， $min\left ( a_i+k-i,k+i-a_i \right )$ 都不小于 $0\leq k< n$ 的情形，所以只需考虑 $0\leq k< n$ 即可。

代码实现：

import sysdef solve():# data = sys.stdin.read().split()# n = int(data[0])# a = list(map(int, data[1:]))n = 10a = [9, 2, 3, 1, 5, 8, 6, 2, 4, 7]ans = float('inf')# 枚举可能的 k 值for k in range(n):total = 0# 对每个位置计算最小操作次数for i in range(1, n + 1):# 直接计算变为 i+k 与 i-k 的代价c1 = abs(a[i - 1] - (i + k))c2 = abs(a[i - 1] - (i - k))total += min(c1, c2)ans = min(ans, total)print(ans)if __name__ == '__main__':solve()

查看全文

http://www.xdnf.cn/news/10765.html