> 若是线形无环，将1-n变为n-1，求逆序数n*(n-1)/2即可(线性代数)
> 但本题由于是环，则在1-n中取一k，将1-n变为形如k-1，n-(k+1)也可满足条件，比如1,2,3,4,5变为3,2,1,5,4也可满足条件。问题转换为只需确定一k，使逆序数最小。
> 设一k，对于k-1和n-(k-1)分别求逆序数：
> k-1：k*(k-1)/2
> n-(k+1):(n-k)*(n-k-1)/2
> 则总共的逆序数为k*(k-1)/2+(n-k)*(n-k-1)/2,根据一元二次方程最低点(-b/2a)求得当k=n/2时该式最小
> 将k=n/2代入k*(k-1)/2+(n-k)*(n-k-1)/2有最小值(n/2)*(n/2-1)(或直接根据最值公式(4ac-b^2)/4a)
> 由于n奇偶不确定将公式变为(n/2)*(n-1)/2可用于奇数的情况，发现对于偶数(n-1)/2=n/2-1，故(n/2)*(n-1)/2适用所有情况，得解
> 
> 
> 写得蛮辛苦，觉得对您有用就UP下吧~本人学识浅薄，如有错误请大家及时指出，以免误导他人

• Re:不错不错 (2) lanxipku 2010-01-22 21:35:51