Skip to content

1168: 发试卷!发试卷!

题目

题目描述

数据结构期末考试结束了,又到了发试卷的时候了。助教组对于如何发放试卷产生了一些内部的争论,因为发放试卷需要走到同学的座位上去,走路是一件痛苦的事情,助教们想要走尽量少的路程来发完所有的试卷。

接下来描述的是一个助教提出的试卷发放策略,你需要帮他计算出发完所有试卷移动的总距离。

为了简化问题,我们规定所有同学都参加了考试,按照学号排成一排,顺次位置的编号为 $1\sim n$。规定位置 $i$, $j$ 之间的路程为 $|i - j|$。每张试卷上都有一个学号 $p_i$,它会被分发到对应的学生手上。

我们定义这个分发试卷的助教有两只手。刚开始,助教站在同学 $s$ 面前,所有的试卷都在助教的左手。发试卷时,助教会用右手拿起左手顶部的一张试卷。

  • 如果这是最后一张需要发的试卷,显然他别无选择,只能走到这张试卷主人的位置上去发这张试卷。
  • 如果他的左手还有试卷,那么他会进行一次比较。
  • 如果发放右手所拿试卷需要走动的距离较长(大于此刻发放左手顶部那张试卷所走路程),他会把右手的试卷直接放到左手所有试卷的最下面,过会再发。此刻并不会发放左手顶部的那张试卷!!!
  • 不然的话,他会直接发掉右手的试卷,并停留在刚发完这张试卷的位置。
  • 无论如何,他都会从左手再拿一张试卷,来进行下一步的决策,直到所有卷子都被发完。

现在,给定试卷的初始顺序序列$p$,以及助教的初始位置 $s$,问他要发完所有试卷走过的总路程是多少。

输入格式

  • 第一行两个正整数 $n, s$ ,分别表示人数和助教的初始位置。
  • 第二行 $n$ 个非负整数,其中第 $i$ 个数表示 $p_i$ ,即从上往下数第 $i$ 张试卷要发到哪里去。

输出格式

输出一个整数,表示需要走的总路程。

样例输入

text 5 1 2 3 1 4 5

样例输出

text 8

数据范围

| 测试点 | n= | 测试点 | n = | | :----: | :-----------: | :----: | :-----------: | | 1 | $3\times10^1$ | 11 | $3\times10^5$ | | 2 | $3\times10^2$ | 12 | $3\times10^5$ | | 3 | $3\times10^2$ | 13 | $3\times10^5$ | | 4 | $3\times10^3$ | 14 | $3\times10^5$ | | 5 | $3\times10^3$ | 15 | $3\times10^5$ | | 6 | $3\times10^3$ | 16 | $3\times10^6$ | | 7 | $3\times10^4$ | 17 | $3\times10^6$ | | 8 | $3\times10^4$ | 18 | $3\times10^6$ | | 9 | $3\times10^4$ | 19 | $3\times10^6$ | | 10 | $3\times10^4$ | 20 | $3\times10^6$ |

  • 对于测试点 $i$ ,你只有通过了所有编号小于等于 $i$ 的测试点,才能获得该测试点的分数。

样例解释

我们用 $L, R, s$ 描述左手试卷的状态,右手试卷的状态以及老师的位置。

| L | R | s | |-----------------|-----|---| | {2, 3, 1, 4, 5} | {} | 1 | | {3, 1, 4, 5} | {2} | 1 | | {3, 1, 4, 5} | {} | 2 | | {1, 4, 5} | {3} | 2 | | {1, 4, 5} | {} | 3 | | {4, 5} | {1} | 3 | | {4, 5, 1} | {} | 3 | | {5, 1} | {4} | 3 | | {5, 1} | {} | 4 | | {1} | {5} | 4 | | {1} | {} | 5 | | {} | {1} | 5 | | {} | {} | 1 |

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!