【Usaco 2010 NOV Gold】奶牛的图片
题目大意:给你一个n的排列,每次可以交换相邻元素,问你最少用多少次能把原序列变成一个首尾相接后存在1~n有序排列的序列。
总结:善于发现移动的不变量。
对于有序化的题目想到逆序对。
发现每次交换相邻的两个位置,逆序对都会变化1.
如果我们要把原序列从小到大排序(逆序对为0)的话。因为要步数最少,那么我们肯定每一次移动,都往对逆序对序列贡献为-1的方向走,每次都能找到这种移动方法,所以最少要用逆序对个数次。
至于首尾相接后的合法序列,我们可以认为1是n + 1, 2是 n + 2依次类推。
当序列最后为 2 3 ... n , 1
等价于 1 - > n + 1
设1的原位置是p, 那么前面比他大的数有p - 1个
变为n + 1后,前面没有比他大的数,后面比他小的数增加了n - p个
所以总逆序对个数增加了n - p - p + 1 个
当最终序列最终为3, 4, 5 .. n 1 2
1变成了n + 1, 2变成了n + 2
可以在上面的基础上,把2 变化即可。
把1变成n +1后,2就成了最小的数
所以变化量一样。
只要维护每个数出现的位置p