题目描述

在一场集体婚礼上，有n对新人需要坐在连续排列的 2n个座位上合影，同一对新人彼此挨着。由于进场时各对新人并未按序入座，请计算最少交换座位的次数，以便使每对新人均可并肩坐在一起。一次交换可选择任意两人，让他们互换座位。
全部新人的序号可用 0 到 2n-1 的整数表示，第一对是 (0, 1)，第二对是 (2, 3)，以此类推，最后一对是 (2n-2, 2n-1)。
row[i]指最初坐在第 i 个座位上的新人编号，i是从0到（2n-1）的一个升序全排列，row不存在重复值。

输入描述

输入共有2行，第一行为n，即共有多少对新人(2≤n≤100000 )，第二行为row，即2n个座位上的初始新人编号。

输出描述:

输出最少交换座位的次数。

思路

pos[i]数组用来记录编号为i的新人坐的位置序号，a[i]数组记录序号为i的位置上坐的新人编号。
从头开始，步进为2的遍历数组a, 固定a[i]的位置，根据a[i]的奇偶得出其另一半的编号y，在pos数组中找到y的座位，与a[i+1]交换，然后修改pos数组中y和a[i+1]的座位信息，依次遍历到数组结束。

提问

为什么这样算出来的就是最小交换次数了呢？

代码

#include<iostream>
using namespace std;

int main() {
    int n, ans = 0;
    cin>>n;
    n *= 2;
    int *a = new int[n], *pos = new int[n];
    for (int i = 0; i < n; ++i) {
        cin>>a[i];
        pos[a[i]] = i;
    }
    for (int i = 0; i < n; i += 2) {
        int x = a[i], y;
        if (x % 2 ) y = x - 1;
        else y = x + 1;
        if (y != a[i + 1]) {
            ans ++;
            pos[a[i + 1]] = pos[y];
            a[pos[y]] = a[i + 1];
            a[i + 1] = y;
            pos[y] = i + 1;
        }
    }
    cout<<ans;
}