#P12700. [KOI 2022 Round 2] 停车场
[KOI 2022 Round 2] 停车场
题目背景
试题来源:https://koi.or.kr/archives/。中文翻译做了少量本土化修改。
按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。
题目描述
有一个圆形的停车塔。停车塔上有 个格子,按顺时针方向依次编号为第 1 个格、第 2 个格、……、第 个格。每个格子中都停有一辆车,第 个格子中的车辆编号为 。
停车塔上有两个按钮:按下按钮 A 会使整个停车塔顺时针旋转一格,按下按钮 B 会使停车塔逆时针旋转一格。下图左边展示了按下按钮 A 后的状态,右边展示了按下按钮 B 后的状态。
此时,目标是将所有车辆从停车塔中依次取出。
车辆只能从最底部的一个格子被取出。初始时,第 1 个格子位于最底部。要取出不在最底部的车辆,必须先按按钮将其旋转至最底部的位置。
此外,编号为 的车辆只能在编号小于 的所有车辆都已被取出的情况下才能被取出。换句话说,如果停车塔中还剩下编号小于 的车辆,那么编号为 的车辆就不能被取出。
请你编写一个程序,计算将所有车辆从停车塔中取出所需按按钮的最少总次数。
输入格式
第一行包含一个整数 。
第二行包含 个整数 ,表示每个格子中车辆的编号,按顺时针顺序排列,以空格分隔。
输出格式
输出一个整数,表示将所有车辆从停车塔中取出所需按按钮的最少总次数。
4
1 2 2 1
3
5
3 1 4 5 1
7
提示
约束条件
子任务
- (8 分)对于所有的 ,。即,所有车辆编号都为 1。
- (9 分)对于所有的 ,有 。即,所有车辆编号各不相同。
- (10 分)
- (21 分)
- (31 分)
- (21 分)无额外约束条件