Skip to content

1380: Rainy Memory的音阶

题目

题目描述

前几天Rainy Memory在逛B站摸鱼时,看到一个大神在玻璃杯中倒入不同体积的水,敲击玻璃杯便能得到音阶,奏出美妙的音乐。虽然已经鸽了几百天,但作为一名严谨的知识区up主,Rainy Memory总能抓住这稍纵即逝的灵感:他新视频的主题,就是定量研究玻璃器皿盛水体积与发出声音的关系!这个idea简直惊为天人,要是这个视频做得好,别说百万播放,今年的百大就是他了!

idea可千万不能被别人先做了!Rainy Memory抓起桌上的 $n$ 个量筒就开始实验。他将各个量筒从 $1$ 到 $n$ 依次编号,初始时先各注入了一些水,可能是太激动了,这个初始注入的液面有高有低。作为严谨的知识区up,Rainy Memory拿出了自己的定量移液枪,一毫升一毫升地从每个量筒里加入或者吸出水。Rainy Memory每秒都能操作移液枪一次,也就是每秒都能使得某一量筒的液面下降一毫升或上升一毫升,Rainy Memory急坏了,他迫切的想知道,最快多少秒以后,这些量筒的装水体积才能变成严格从小到大

早日发视频,上首页,上日榜,上推荐,拿百大,Rainy Memory的up主梦就靠你了!

输入格式

第一行一个整数 $n$​​ ,代表量筒数量。

第二行包含 $n$ 个整数$a_i$,代表每个量筒初始的水面刻度。单位都是毫升。

输出格式

一个正整数 $x$​​​​,代表最少所需操作步数。

样例输入

样例输入 1

text 7 2 1 5 11 5 9 11

样例输出 1

text 9

样例输出 1 的解释

最终量筒的液面高度:

text 2 3 5 6 7 9 11

$∣2−2∣+∣1−3∣+∣5−5∣+∣11−6∣+∣5−7∣+∣9−9∣+∣11−11∣=9$

样例输入 2

text 5 5 4 3 2 1

样例输出 2

text 12

样例输出 2 的解释

最终量筒的液面高度:

text 1 2 3 4 5

$∣5−1∣+∣4−2∣+∣3−3∣+∣2−4∣+∣1−5∣=12$

数据范围

对于50%的数据,$1 \leq n \leq 3000$​​。

对于100%的数据, $1 \leq n \leq 2 \times 10^6$​,$1 \leq a_i \leq 10^9$​

值得注意的是,Rainy Memory会膜法,因此液面高度调整为0、甚至是为负都认为是合法的情况!(毕竟在任何时刻给所有量筒加等量的水是很容易的事情吧,我猜?~~会魔法真可怕~~)

Oops! 本题目还没有解答!

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

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

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