昨天我们做了清华的预选赛，沈大、梁老大、肖叉各搞定一道题，险些跌出60名。我做了B和F，其中F是关于逆序数的题目，复杂度是 nlog2n+mn 最差的复杂度可能降为O(n^2)。但我提交的结果不是TLE，而是MLE和RE。真不知道是清华判题系统有问题还是我的程序有问题。总之，我心有不服啊，所以决定今天花点时间归纳一下“逆序对”的题目，给大家写份报告，提供点资料。 首先，逆序对（inversion pair）是指在序列{a0,a1,a2...an}中，若ai<aj(i>j)，则(ai,aj)上一对逆序对。而逆序数（inversion number）顾名思义就是序列中逆序对的个数。例如： 1 2 3是顺序，则逆序数是0；1 3 2中(2,3)满足逆序对的条件，所以逆序数只有1； 3 2 1中(1,2)(1,3)(2,3)满足逆序对，所以逆序是3。由定义不能想象，序列n的逆序数范围在[0,n*(n-1)/2]，其中顺序时逆序数为0，完全逆序时逆序数是n*(n-1)/2。

目前我知道的求逆序最快的适合ACM/ICPC的算法是归并排序时计算逆序个数，时间复杂度是nlog2n，而空间复杂度2n。JAVA模板（服务器是校内的）。

归并求逆序简单原理：
归并排序是分治的思想，具体原理自己去看书吧。利用归并求逆序是指在对子序列 s1和s2在归并时，若s1[i]>s2[j]（逆序状况），则逆序数加上s1.length-i,因为s1中i后面的数字对于s2[j]都是逆序的。

TJU 2242:
直接上模板，记得m的奇偶要考虑的哦。

PKU 1007:
求逆序数，然后排序输出就行了。

PKU 1804, PKU 2299:
是最简单的关于逆序对的题目，题目大意是给出一个序列，求最少移动多少步可能使它顺序，规定只能相邻移动。
相邻移动的话，假设a b 相邻，若a<b 交换会增加逆序数，所以最好不要做此交换；若a==b 交换无意思，也不要进行此交换；a>b时，交换会减少逆序，使序列更顺序，所以做交换。
由上可知，所谓的移动只有一种情况，即a>b，且一次移动的结果是逆序减1。假设初始逆序是n，每次移动减1，那么就需要n次移动时序列变为顺序。所以题目转化为直接求序列的逆序便可以了。

ZJU 1481:
这题和本次预选赛的F略有相似，不过要简单得多。题意是给定序列s，然后依次将序列首项移至序列尾，这样共有n-1次操作便回到了原序列（操作类似于循环左移）。问这n-1次操作和原序列，他们的逆序数最小的一次是多少？
有模板在手，直观地可以想到是，对于这n次都求逆序数，然后输出最小的一次就可以了，但这样做的复杂度有O(n*nlogn),太过复杂。
如果只求初始序列的逆序数的话，只要后面的n-1次操作的逆序数能够在O(1)的算法下求得，就能保证总体O(nlogn)的复杂度了。事实上，对于每次操作确实可以用O(1)的算法求得逆序数。将序列中ai移到aj的后面，就是ai做j-i次与右邻的交换，而每次交换有三个结果：逆序+1、逆序-1、逆序不变。由于题目中说明序列中无相同项，所以逆序不变可以忽略。逆序的加减是看ai与aj间（包括aj）的数字大小关系，所以求出ai与aj间大于ai的数字个数和小于ai的数字个数然后取差，就是ai移动到aj后面所导致的逆序值变化了。
依据上面的道理，因为题目有要求ai是移动到最后一个数，而ai又必定是头项，所以只要计算大于ai的个数和小于ai的个数之差就行了。然后每次对于前一次的逆序数加上这个差，就是经过这次操作后的逆序数值了。

PKU 2086:
这题不是求逆序对，而是知道逆序数k来制造一个序列。要求序列最小，两个序列比较大小是自左向右依次比较项，拥有较大项的序列大。
其实造序列并不难，由1804可知，只要对相邻数做调整就能做到某个逆序数了。难点是在求最小的序列。举例 1 2 3 4 5,要求逆序1的最小序列是交换4 5，如果交换其他任意相邻数都无法保证最小。由此可以想到，要保证序列最小，前部分序列可以不动（因为他们已经是最小的了），只改动后半部分。而我们知道n个数的最大逆序数是n*(n-1)/2，所以可以求一个最小的p，使得 k<p*(p-1)/2。得到前半部分是1到n-p，所有的逆序都是由后半部分p个数完成的。
考虑k=7,n=6的情况，求得p=5,即前部分1不动，后面5个数字调整。4个数的最大逆序是5 4 3 2,逆序数是6，5个数是6 5 4 3 2,逆序数是10。可以猜想到，保证5中4个数的逆序不动，调整另一个数的位置就可以增加或减少逆序数，这样就能调整出6-10间的任意逆序。为了保证最小，我们可以取尽量小的数前移到最左的位置就行了。2前移后逆序调整4，3前移后调整了3，4调整2，5调整1，不动是调整0，可以通过这样调整得到出6-10，所以规律就是找到需要调整的数，剩下的部分就逆序输出。需要调整的数可以通过总逆序k-(p-1)*(p-2)/2+(n-p)求得。

PKU 1455:
这是一道比较难的关于逆序数推理的题目，题目要求是n人组成一个环，求做相邻交换的操作最少多少次可以使每个人左右的邻居互换，即原先左边的到右边去，原右边的去左边。容易想到的是给n个人编号，从1..n，那么初始态是1..n然后n右边是1，目标态是n..1，n左边是1。
初步看上去好象结果就是求下逆序（n*(n-1)/2 ?），但是难点是此题的序列是一个环。在环的情况下，可以减少许多次移动。先从非环的情况思考，原1-n的序列要转化成n-1的序列，就是做n(n-1)/2次操作。因为是环，所以(k)..1,n..k+1也可以算是目标态。例如：1 2 3 4 5 6的目标可以是 6 5 4 3 2 1,也可以是 4 3 2 1 6 5。所以，问题可以转化为求形如(k)..1,n..k+1的目标态中k取何值时，逆序数最小。
经过上面的步骤，问题已经和ZJU1481类似的。但其实，还是有规律可循的。对于某k，他的逆序数是左边的逆序数+右边的逆序数，也就是(k*(k-1)/2)+((n-k)*(n-k-1)/2) （k>=1 && k<=n）。展开一下，可以求得k等于n/2时逆序数最小为((n*n-n)/2)，现在把k代入进去就可以得到解了。
要注意的是k是整数，n/2不一定是整数，所以公式还有修改的余地，可以通用地改为(n/2)*(n-1)/2。

PKU 2893:
用到了求逆序数的思想，但针对题目还有优化，可见M*N PUZZLE的优化。

PKU 1077:
比较经典的搜索题，但在判断无解的情况下，逆序数帮了大忙，可见八数码实验报告。

 

本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/ray58750034/archive/2006/10/08/1325939.aspx

本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/ray58750034/archive/2006/10/08/1325939.aspx

本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/ray58750034/archive/2006/10/08/1325939.aspx

//

//

1. pku 1700 Crossing River (pku 3404 Bridge over a rough river)

就是最朴素的过桥问题，问最少所需时间

2. pku 2573 Bridge

在1的基础上加上过桥所需要的步骤

3. zju 1579 Bridge 

这里要用long long 真恶

4. hit 2540 Only One Boat

这个题目是过桥问题的变种,题目的意思就是有N队夫妻,现在要过河，但是只有一条船，并且船每次只能载两个人。要求每一个妻子不能在丈夫不在的情况下与其他男人在一起，无论是船上还是岸上都不可以。问最少的次数使得所有人过河，并打印具体的步骤(spj)。

这个问题最少次数其实是固定的，不难推出如果有n队夫妻，那么全部过河的最少次数是5*n-3。（这个原因我请教了这个题目的作者，他的意思是最优的策略一定是两个人坐船去彼岸，一个人坐船回此岸。因此最少次数是一定的)。知道了最少次数如何去打印具体步骤了，其实我们从样例中3队夫妻的说明中可以得到一些启发，就是说经过若干步之后可以使得一对夫妻"Leave"。 例如3队夫妻的时候，标号为1，2为第一对夫妻（奇数为男，偶数为女，下同）,标号为3，4为第二对夫妻，标号为5，6为第三对夫妻。那么由2，4首先坐船来到彼岸，然后2回去，2和6再来到彼岸回去，然后6回去，让1，3过来，然后1和2离开，3回头，3和5再过去，3和4离开，5回头，5和6过河并离开。 现在转换到n个人的情形。如果n=1或者2，那么很容易就能找到方案了，因此下面的情况针对n>=3的情况，我们可以先让2n和2n-2过河，然后2n回来。(注：这个时候所形成的局面是此岸有n-1对夫妻和一个丈夫，彼岸有一个该丈夫的妻子）。下面2n和2n-4过河，然后2n-4回来，2n-1和2n-3过河，2n和2n-1 离开，2n-3返回。（注：这个时候的局面是此案有n-2对夫妻和一个丈夫，彼岸有一个该丈夫的妻子）。可以看出这是一个递归的过程。下面实现就简单了。

5. zju 2288 Across the River

题目大意: n个男生和m个女生过河.只有一只船,船每次最多装k人且满足如下条件:

任何时候岸边(包括此岸和彼岸)和船上要么没女生.否则女生不比男生少，问最少要渡几次才能使得所有人渡河完毕。

这个题目如果没有说要求彼岸也满足这个要求（即女生不比男生少，或者没有女生），我们可以利用贪心算法解决。

可以总是先把男生给送到彼岸，然后剩下来的部分都是尽量在满足条件的情况下把男生往船上放，然后每次把船从彼岸送回来的人最好是女生。这样可以使得结果次数最少。

但是现在要求的是此案和彼岸都必须满足条件，这样的话我们就只能bfs搜了。数据量不算大。

结论一：？哪去了？

结论二：
一定有这样一种最佳方案，在这个方案里，所有从彼岸到此岸的移动只需一个人。　　如果最佳方案中有一步中需要两个人从彼岸移动到此岸，那么我们可以把这一步改为只移动比较快的那个人。

结论三：
一定有这样一种符合结论二的最佳方案，在这个方案里，所有从彼岸到此岸的移动中，回来的这个人一定是当时在彼岸所有人中速度最快的。　

结论四：
一定有这样一种符合结论二—三的最佳方案，在这个方案里，每当出现手电筒在此岸的局面时，速度最快的那个人总是在此岸。

结论五：
一定有这样一种符合结论二—四的最佳方案，在这个方案里，所有从此岸到彼岸的移动都需两个人。

结论六：
一定有这样一种符合结论二—五的最佳方案，在这个方案里，每次从此岸到彼岸移动两人，要么这两人里有一个是所有人中最快的那个，要么这两人到达彼岸后都再也不回来。　　　

结论七：
一定有这样一种符合结论二—六的最佳方案，在这个方案里，所有从彼岸到此岸的移动中，回来的这个人一定是当时在彼岸所有人中速度最快的，而且他只能是所有人中最快的或者次快的。　
换句话说，所有返回此岸的任务都可以只由跑得最快和跑得次快的人来担当，所有其他人一旦到达彼岸，就留在那里，再也不回来。

结论八：
一定有这样一种符合结论二—七的最佳方案，在这个方案里，所有除了最快和次快的旅行者都以上面两个模式过桥，并且再不回来。

假设A为最快，B为次快，而Z是任意一个其他旅行者。
模式一:由A护送到Z对岸，A返回
模式二:AB->,A<-,YZ->,B<-

结论九：所有符合结论八的最佳方案中，最慢两人过桥的模式必须相同，而且如果使用的都是模式二，那么他们一定在一起过河。

结论　
　如果给定N个（速度不同）的旅行者，根据结论九我们知道有一个最佳方案，在最初的4步里用模式一或模式二把最慢的两个旅行者移动到彼岸，于是问题被约化成N-2个旅行者的形式。问题在于应该选择哪一种模式。继续假设A、B为走得最快和次快的旅行者，过桥所需时间分别为a、b；而Z、Y为走得最慢和次慢的旅行者，过桥所需时间分别为z、y。　　
在第六节中我们发现
使用模式一移动Z和Y到彼岸所需的时间为：z + a + y + a
使用模式二移动Z和Y到彼岸所需的时间为：b + a + z + b
所以，　　　
当2b＞a+y时，应该使用模式一；
当2b＜a+y时，应该使用模式二　
当2b＝a+y时，使用模式一或二都可以。　　
上面的讨论都是在N≥4时进行的，那时最快、次快、最慢和次慢是四个不同的人。所以我们还要稍微讨论一下N=1、2、3的情况。　　N=1、2是不用动脑子的，直接通通过桥就是了。　
N=3也很简单，用穷举法可以发现由最快的人往返一次把其他两人送过河是最快的方法。　　
于是我们得到了最终结论：最佳方案构造法：
以下是构造N个人(N≥1)过桥最佳方案的方法：　　
1) 如果N=1、2，所有人直接过桥。　　
2) 如果N=3，由最快的人往返一次把其他两人送过河。　
3) 如果N≥4，设A、B为走得最快和次快的旅行者，过桥所需时间分别为a、b；而Z、Y为走得最慢和次慢的旅行者，过桥所需时间分别为z、y。
那么　　
当2b＞a+y时，使用模式一将Z和Y移动过桥；　　　　
当2b＜a+y时，使用模式二将Z和Y移动过桥；　　　
当2b＝a+y时，使用模式一将Z和Y移动过桥。
这样就使问题转变为N-2个旅行者的情形，从而递归解决之。　
　最后当然我们要举一个具体的例子：七个旅行者，所需过桥时间分别是1、4、5、5、5、8、9分钟。　　
我们假设他们顺次为A、B、C、D、E、F、G，我们注意到C、D、E的速度一样，用第二节的方法太正规也太麻烦，我们可以人为规定C速度稍稍大于D，D速度又稍稍大于E。
采用结论十的方法，最快和次快的是A、B，时间为1和4；最慢和次慢的是G和F，时间为9和8。
现在2*4＜1+9，所以用模式二：
第1步：　　　　　　A B →　　4
第2步：　　　　　　　A ←　　1
第3步：　　　　　　F G →　　9
第4步：　　　　　　　B ←　　4
现在剩下A、B、C、D、E在此岸，最快和次快的是A、B，时间为1和4；最慢和次慢的是E和D，时间为5和5。
现在2*4＞1+5，所以用模式一：
第5步：　　　　　　A E →　　5
第6步：　　　　　　　A ←　　1
第7步：　　　　　　A D →　　5
第8步：　　　　　　　A ←　　1
现在剩下A、B、C在此岸，用N=3的办法结束：
第9步：　　　　　　A C →　　5
第10步：　　　　　　 A ←　　1
第11步：　　　　　 A B →　　4
总的时间为　　　　4+1+9+4+5+1+5+1+5+1+4 = 40分钟
虽然我一个其他的方案都没列举，我知道这个40分钟的方案必定是最佳的。

//呵呵 //找规律，类似斐波那契数列
//每对顶点之间的最短路径算法floyd，其实是动归，O(n³)，还要注意disjoint