#P1137. 2023.04.01-第一题-整理
2023.04.01-第一题-整理
![](https://s3.bmp.ovh/imgs/2024/09/03/9ec1757951030a02.jpg)
塔子哥是一个非常有个性的人,他对待装饰品摆放方式的审美角度很奇特。他认为高度相差比较大的装饰品放在相邻位置会很难看。最近,他正在整理桌子上的一排装饰品,但是发现它们的位置摆放得不太好看。于是,他想对这排装饰品进行整理,可以交换任意两个装饰品的位置任意多次,以便让它们看起来更加美观。
假设当前从左到右 n 个装饰品的高度分别为 h1,h2,…,hn 那么当前这一排装饰品的丑陋值为 ∑i=1n−1∣hi−hi+1∣ ,其中 ∣x∣ 为 x 的绝对值。塔子哥不想他的装饰品看起来很丑陋,他想最小化他的装饰品的丑陋值,请你帮他排一下顺序。
形式化地来讲,有一长为 n 的序列 a1,a2,…,an ,你可以任意次数地进行交换,每次交换都可以选择任意两个不同的数 i,j ,交换 ai,aj 的位置。
假设经过若干次交换后,序列变为 h1,h2,...,hn 其丑陋值为 ∑i=1n−1∣hi−hi+1∣ ,你需要找出一种交换方式,使得最终序列 {hn} 的丑陋值最小化。
你不需要输出具体交换,只需要输出最终的 {hn} 序列的丑陋值即可。
第一行一个整数 n ,表示塔子哥的装饰品数量。
接下来一行 n 个整数 a1,a2,…,an ,依次表示从左到右 n 个装饰品的高度。
对于所有的数据: 2≤N≤50000 , 0≤ai≤109 。
输出第一行一个数,为最优方案的最小丑陋值。
输入
3
3 1 2
输出
2
样例解释 我们可以将3和1交换,得到
1 3 2
然后再将2和3交换,得到
1 2 3
可以证明,此时有最小丑陋值 ∣1−2∣+∣2−3∣=2
扫码备注加群即可,期待您的到来~
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.