本文最后更新于 722 天前,其中的信息可能已经有所发展或是发生改变。
思想:
- 前缀和。
- 由于牛棚为环状,故将数组首尾相连。
- 利用
sum
记录牛牛们需要走的距离,前缀和记录a[i]
扇门i ~ n
的距离。 - 从连接后的数组开始,即
i = n ~ 2 * n
开始遍历,sum
减去后一个房间牛牛走过的距离,再加上该房间牛牛走到i + n
的距离。 - 维护一个最小的
ans = min(ans, sum)
即可。
代码:
思想:
sum
记录牛牛们需要走的距离,前缀和记录 a[i]
扇门 i ~ n
的距离。i = n ~ 2 * n
开始遍历,sum
减去后一个房间牛牛走过的距离,再加上该房间牛牛走到 i + n
的距离。ans = min(ans, sum)
即可。代码: