题意分析​

本题中，奶牛们的晾衣绳在顶部和底部固定架上的槽位排列混乱，需要通过交换相邻绳头来整理。每根晾衣绳有唯一编号，输入给出了顶部固定架每个槽位对应的绳编号和底部固定架每个槽位对应的绳编号。我们的目标是找到最小的相邻交换次数，使得整理后同一根绳在顶部和底部的槽位编号相同（即顶部槽 i 和底部槽 i 对应同一根绳）。关键在于理解：无论选择调整顶部还是底部的排列，最小交换次数等价于将某一端的排列转换为有序序列所需的相邻交换次数。​

解题思路​

建立映射关系：首先需要确定每根绳在顶部和底部固定架上的初始位置。可以通过输入数据建立一个映射，记录每根绳在底部固定架上的槽位编号，这样就能知道当顶部排列有序时，底部各绳应该处于什么位置。 ​

构造目标排列：假设我们以顶部固定架的槽位顺序为基准，希望顶部槽 1 到槽 N 依次对应绳 1 到绳 N。那么根据映射关系，底部固定架上各槽位应该对应的绳编号就可以确定，从而构造出底部固定架的目标排列。 ​

计算逆序数：相邻交换次数等于排列中的逆序对数量。逆序对是指在排列中，前面的数比后面的数大的情况。因此，我们需要计算构造出的底部目标排列的逆序数，这个逆序数就是所需的最小相邻交换次数。 ​

具体步骤： ​ 遍历输入数据，记录每根绳在底部固定架上的槽位编号，建立绳编号到槽位编号的映射。​

构造底部固定架的目标排列：对于顶部槽 i（i 从 1 到 N），目标绳编号为 i，根据映射找到该绳在底部固定架上的槽位编号，组成一个新的排列。​

计算这个新排列的逆序数，即为所求的最小交换次数。

代码

#include <iostream>
#include <cmath>
#include <algorithm>
#include <stdio.h>
#include <string.h>
 
#define MAXINT 1111
#define LENGTH 1111
 
void Merge_sort(int a[LENGTH], int p, int r);
void Merge(int a[LENGTH], int p, int q, int r);
 
int inve_sum = 0;
 
int main(void)
{
	int top[LENGTH], bottom[LENGTH], a[LENGTH];
	int N;
 
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
 
    while(scanf("%d", &N)!= EOF){
    	for (int i = 0;i < N;i ++){
        	scanf("%d %d", &top[i], &bottom[i]);
    	}
    	for (int i = 0;i < N;i ++){
        		for (int j = 0;j < N;j ++){
            		if (top[i] == bottom[j]){
                			a[i] = j;
				break;
			}
        		}
    	}
	inve_sum = 0;
    	Merge_sort(a, 0, N - 1);
    	printf("%d\n", inve_sum);
    }
    return 1;
}
 
void Merge_sort(int a[LENGTH], int p, int r){
    int q;
    if (p < r){
        q = (p + r) >> 1;
        Merge_sort(a, p, q);
        Merge_sort(a, q + 1, r);
        Merge(a, p, q, r);
    }
}
 
void Merge(int a[LENGTH], int p, int q, int r){
    int L[(LENGTH >> 1) + 1], R[(LENGTH >> 1) + 1];
    int n1 = 0, n2 = 0;
 
    for (int i = p;i <= q;i ++){
        L[n1++] = a[i];
    }
    L[n1] = MAXINT;
 
    for (int i = q + 1;i <= r;i ++){
        R[n2++] = a[i];
    }
    R[n2] = MAXINT;
 
    n1 = 0, n2 = 0;
    for (int k = p;k <= r; k++){
        if (L[n1] <= R[n2]){
            a[k] = L[n1];
            n1++;
        }else{
            a[k] = R[n2];
            inve_sum += q - p + 1 - n1;
            n2++;
        }
    }
}
 
```

```