勇闯黄金十二宫系列--双子宫(大家快来闯宫啊,救活雅典娜)

Question

小弟在五一期间每天会发一到两个宫的题,给各位大哥解解闷,顺便结识一些对算法感兴趣的朋友.望大家都能闯过十二宫.大家闯宫成功后请把答案写在回复中,以便让大家分享.Problem
第三个他们来到双子宫，身为双子座黄金圣斗士的撒加其实就是假教皇，他在教庭使用念力把双子宫布置成了一个迷宫，里面有n个敌人，手拿斧头。（当然都是幻影）星矢他们四人兵分两路。由于紫龙的眼睛暂时瞎了，他用心感悟到这是个迷宫，于是便带星矢很轻松地通过了。而冰河和阿瞬却陷入了苦战。冰河又被撒加的二次元空间打到了天秤宫。此时只剩下阿瞬一人。 此时阿瞬面前有n个人，用1..n标号，现在他们每人手里拿着一个斧子。这些斧子都是他们自己的，不过斧子的顺序打乱了，每个人拿的不一定是自己的斧子。（如1号人可能拿着2号斧子）这n个斧子也用1..n标号。阿瞬通过星云锁链感应到，要想突破迷宫，唯一的方法是用最短时间，使得他们都拿到自己的斧子。每一个时间单位一个人可以不做任何动作，也可以与另外一个人交换斧子。求最少交换次数和最短所用时间。你能帮阿瞬突破迷宫吗？Input
本题包含多组数据. 第1行，为n(2<=n<=20000) 下面n行，每行1个数，表示第i个人手里拿的斧子的编号。 Output
对于每组数据输出一行，为两个数，最少交换次数和最短所用时间。 Sample Input
4--表示共有4个人
2--表示一号人拿着二号斧子
1--表示二号人拿着一号斧子
4--表示三号人拿着四号斧子
3--表示四号人拿着三号斧子Sample Output
2--表示最少需要交换两次 1--表示最短需要一个时间单位

Answer 1

喜欢双子，顶一下，解题就没有兴趣了，因为自己的程序都还没有写完

Answer 2

清华的数据结构里面好像有这种问题，好像是战士拿枪

Answer 3

想了一下，
1可以先算出整个数列的逆序数，这个数就是要交换的次数，然后用一个循环，直到逆序数为零退出，每次循环都算出不在正确位置上的数的个数，可以交换的就是这些数，然后把逆序数减去这些数的个数除以2，最后循环的次数就是时间单位。
比如2 1 4 3 逆序数为2，

Answer 4

计算逆序数是不对的，
比如：4 3 2 1 逆序数是6，而实际上只要交换2次

Answer 5

应该计算置换群的轮换，应该将每个轮换的长度减1，再加起来，就是交换次数。