总览
N对情侣希望坐在2N个座位上，每个情侣希望坐到相邻的位置，请通过最少次的座位交换达成此目的。
贪心算法
本题目看似可以进行状态搜索，但实际上状态空间十分巨大，很难做到。直观来看，每一次交换至少可以使一对情侣坐到一起，且至多可使两对情侣坐到一起。
很容易想到如下贪心策略：
- 每次令最左边的一对情侣坐到一起，将其移出，重复此操作直至所有情侣都坐到一起。
事实上这个策略是正确的，您可能会有一些顾虑，例如
- 当次交换可能可使两对情侣坐到一起，但却没有执行这个操作。
- 可能存在更好的交换选择，使得后面尽可能多地出现“能恰好使两对情侣坐到一起”的情况。
对于1，可以想到的是即使当次没有那两对情侣，但这并不影响后面进行这步操作，因为当次交换一定不会涉及到互相坐错的两对情侣的位置。
对于2，实际上这种情况并不存在。一次交换至多产生两个“相互坐错”的情况，但仅当当次交换是一次无用的交换（没有使任何情侣坐到一起），才有可能产生两个“相互坐错”，这种情况下算上这次无用的交换依然要交换三次，因此有用的交换至少不会比无用的交换差；其次如果某个交换能够产生一个“相互坐错”，其他情侣的配对并不会影响到这个交换之后的实施，因此这样做是没有问题的。