AlgoMooc
← 返回题库

K0093. 秘环符文的最短行走

简单通过率 72% · 提交 18 · 通过 13
模拟数学贪心

小慕正在开发一个环形数据缓存系统,缓存中有 `m` 个存储节点(下标从 `0` 到 `m-1`),每个节点存放着一个唯一的数据块编号,恰好是 `1..m` 的一个。 小慕需要从数据块 `1` 开始,按顺序依次访问数据块: `1 -> 2 -> 3 -> ... -> m` 当小慕从当前数据块所在的节点移动到下一个目标数据块所在的节点时,可以沿环形缓存: * 顺时针移动(下标递增,超过 `m-1` 后回到 `0`) * 逆时针移动(下标递减,小于 `0` 后回到 `m-1`) 一次移动的步数定义为:沿某个方向从 `curr_idx` 走到 `target_idx` 需要经过的“相邻节点间隔数”(也就是移动次数)。小慕每一步都选择更短的方向,其最短步数为: `d = abs(curr_idx - target_idx)` `step = min(d, m - d)` 请计算从 `1` 访问到 `m` 的整个过程中,所有步数之和。

提示:带虚线的词点一下有通俗解释。

输入描述

* 第一行:一个整数 `m`,表示传送门数量。 * 第二行:`m` 个整数,表示乱序的符文排列 `glyphs[0..m-1]`。 输入保证 `glyphs` 是 `1..m` 的一个排列(每个数字恰好出现一次)。 * `2 <= m <= 100` * `glyphs` 为 `1..m` 的排列

输出描述

输出一个整数,表示按 `1 -> 2 -> ... -> m` 遍历时,每一步最短移动步数的总和。

示例

示例 1

输入

7
3 7 1 5 2 6 4

输出

14

说明:符文位置(值 -> 下标)为: `1->2, 2->4, 3->0, 4->6, 5->3, 6->5, 7->1` * `1(2) -> 2(4)`:`min(2, 5)=2` * `2(4) -> 3(0)`:`min(4, 3)=3` * `3(0) -> 4(6)`:`min(6, 1)=1` * `4(6) -> 5(3)`:`min(3, 4)=3` * `5(3) -> 6(5)`:`min(2, 5)=2` * `6(5) -> 7(1)`:`min(4, 3)=3` 总和:`2+3+1+3+2+3 = 14`

时间限制 1000 ms · 内存限制 128 MB

看不懂题目?点开图解(训练营专属)

登录后查看题目图解

题目图解为训练营学员专属内容,请先登录。

微信扫码登录还不是训练营学员?了解训练营 →
写完代码点「提交」,将对全部测试用例判题。