题目描述：
电影院有一排有2n个座位, 上面坐了n对情侣. 情侣并不是很开心, 因为电影院的座位票是随便发的. 不是每个人都坐在自己的另一半的旁边. 所以情侣决定交换座位. 任意两个人可以交换座位. 每次只能有两个人交换. 交换完成之后才能再有下一次交换.
Input:
array a[0..2n-1]. 其中a[i]=a[j]=k说明位置i,j上坐着第k对情侣. k=1,..,n.
output:
一个交换列表, 使得用最少的交换可以让每个情侣坐在一起, 并且每个人移动最多一次.
我的思路：
没有测试数据，没法验证思路是否正确，如果发现有过不去的数据，在留言上帮忙写下，谢谢咯~
1. 我们认为电影院的座位从1开始编号（题目上貌似是从0，额……不改了）。假设移动完成后，一对情侣的位置分别为a和a+1，那么a必须为奇数，因为如果a为偶数，前面就有奇数个座位，肯定会有灯泡的……
2. 从前到后开始扫描奇数位置，找到不和后面配对的人x。
3. 然后将x+1换走，换来x的情侣。这时候，x+1被换过一次，那么x+1就不能再被换了，因此只能换来x+1的情侣。根据上面第1条，如果x+1在奇数位置，那么就将x+1的情侣换到x+1后面，否则，换到x+1前面。被换走的人重复这个过程，直到没人可换。继续进行2中的扫描，直到最后。
4. 以上其实有两种方案，一种是将x换走，在x这个位置换来x+1的情侣。另一种是将x+1换走，在x+1这个位置换来x的情侣。这两种方案实际上步骤数是一样的，实际上最终结果只有x这个情侣对和x+1这个情侣对位置互换而已，可以自己换下看看。
5. 整个算法的时间复杂度是O(n)的，应该是最优的，因为有题上的约束条件，只能这么换…… 另外构图什么的O(n)过程，见代码。在步3中，某个节点最多访问两次（2步骤一次，换一次），所以也是O(n)的。详细代码见下：
#include <iostream> #include <cstring> #define SEATMAX 10000 using namespace std; int lover[SEATMAX+1],n; int findPair[SEATMAX/2+1],thePair[SEATMAX+1]; // 辅助配对 void swap(int a, int b) { int tmp=lover[a]; lover[a]=lover[b]; lover[b]=tmp; cout<<"swap person in position "<<a<<" and "<<b<<endl; } void solve() { for(int i=1;i<=n;i++) { // 找到自己的情侣 int k=lover[i]; if(findPair[k]=!0) { thePair[i]=findPair[k]; thePair[findPair[k]]=i; } else findPair[k]=i; } for(int i=1;i<n;i+=2) { // 交换过程 int cur=i; int theLover=thePair[cur]; while(true) { int curLoverPos; if(cur%2==0) curLoverPos=cur-1; else curLoverPos=cur+1; if(lover[cur]==lover[curLoverPos]) break; swap(curLoverPos,theLover); cur=theLover; theLover=thePair[curLoverPos]; } } } int main() { cin>>n; memset(findPair,0,sizeof(findPair)); for(int i=1;i<=n;i++) cin>>lover[i]; solve(); return 0; }