[逆序数对的应用]CSU暑假集训组队赛第一题

这次题目比较坑爹.因为我们的时间确实比较紧,半天需要找9道题.后来是刘悠然一人在USACO的月赛中找了9题.结果新人大受打击,一片一题.

第一题的题意是,给你一个1 2 3。。。n的乱序列,让你用最少的交换步数得到下面的样子[其中交换只能在相邻的两个数里面进行]—–所以的i在i+1的左边,然后n在1的左边.当然序列的最后一个数算是第一个数的左边.也就是说如果是1 2 3 4 5的话,那么

1 2 3 4 5 | 2 3 4 5 1 | 3 4 5 1 2 | 4 5 1 2 3 | 5 1 2 3 4都算符合条件的序列

这题的解法就用到了逆序数对,因为一个序列如果只能通过相邻的两个交换使之变成1 2 3 4….n这样的序列的话,那么结果和逆序数对是一样的.这个可以证明.然后这题就可以用逆序数对来解决了.首先我们知道对于一个序列循环左移一位就相当于把最小的数加上n,然后又变成了从小到大的一个排列.还有对于一个序列中最小的一个数,如果加上n的话,那么这个序列的逆序数将变为L+(n-p)-(p-1)这里L是原序列的逆序数对,n是数目的个数,p是最小的数字的位置,从1开始.这样我们就可以首先求出变换到1 2 3….n的步数,也就是逆序数对,然后依次把i变换为i+n(i从1开始到n-1).这样这题就变成了n*lgn的了.可以解决之