题解：AT_arc194_b [ARC194B] Minimum Cost Sort

· · 题解

AT_arc194_b [ARC194B] Minimum Cost Sort

题意

给定一个排列，可交换相邻相邻两项，付出的代价为靠左一项的值。求排好序所需最小代价。

做法

这就是一个冒泡排序。

发现每次交换两个数一定会减小逆序对，证明显然。考虑对 n 进行归位处理。发现如果把 n 扔到左边一定会增加逆序对数，所以 n 一定会先移到最后。

发现可以把其化为子问题或者递归去求解。

考虑代价的计算。发现只需找到左边比当前数大的数即可。

树状数组维护即可。