题目分析本题描述了一个经典的列车车厢重排问题。在一个老式火车站中有一种特殊的工作称为 “列车交换员” Train Swapper\texttt{Train Swapper}Train Swapper其工作是通过交换相邻车厢的位置将列车车厢按照编号111到LLL的顺序排列。题目要求计算将给定序列通过相邻交换排序所需的最少交换次数。实际上这个问题等价于计算一个排列的逆序对数。因为每次交换相邻两个元素可以消除恰好一个逆序而最少交换次数就等于原始排列中的逆序总数。逆序的定义在一个序列中如果存在一对下标iji jij满足a[i]a[j]a[i] a[j]a[i]a[j]则称(i,j)(i, j)(i,j)为一个逆序对。解题思路题目中给出的两个代码实现了两种不同的方法来计算最少交换次数。方法一冒泡排序统计交换次数第一个代码直接模拟了冒泡排序的过程并在每次交换相邻元素时累加计数器。由于冒泡排序每次比较并交换相邻逆序对最终的交换次数就等于逆序对数。算法步骤从最后一个位置开始逐轮将当前未排序部分的最大元素 “冒泡” 到末尾。在每一轮中从左到右比较相邻元素如果前一个大于后一个则交换并增加计数。最终计数即为最少交换次数。这种方法的时间复杂度为O(L2)O(L^2)O(L2)由于L≤50L \leq 50L≤50完全可行。方法二依次寻找最小元素并移动到前面第二个代码采用了另一种思路按照编号1,2,…,L1, 2, \dots, L1,2,…,L的顺序依次将当前需要的车厢 “移动” 到序列的前面。每次找到目标车厢的当前位置将其移动到前面所需交换的次数等于它当前的位置索引假设从000开始计数然后将该车厢从序列中删除。算法步骤对于iii从111到LLL在当前序列中查找数值为iii的元素得到其下标jjj从000开始。将jjj累加到答案中因为需要将iii经过jjj次相邻交换移动到最前面。从序列中删除该元素。输出累加的总和。这个方法本质上也是在计算逆序数因为将元素iii移动到前面需要经过它前面的所有元素而这些元素都与iii构成了逆序对。两种方法的比较方法核心思想时间复杂度代码简洁度冒泡排序模拟冒泡统计交换次数O(L2)O(L^2)O(L2)较简单删除法依次查找最小元素并删除O(L2)O(L^2)O(L2)稍复杂两种方法都能正确求解且对于L≤50L \leq 50L≤50的数据范围都足够高效。代码实现// Train Swapping// UVa ID: 299// Verdict: Accepted// Submission Date: 2016-05-09// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;vectorinttrains;// 存储当前车厢序列// 使用冒泡排序统计最少相邻交换次数即逆序对数intsortAndCount(){intswaps0;// 交换次数计数器// 外层循环一共需要进行 L-1 轮冒泡for(intitrains.size()-1;i0;i--)// 内层循环将当前轮次中最大的元素向右移动for(intj0;ji;j)// 如果相邻两个元素逆序则交换并计数if(trains[j]trains[j1]){swaps;swap(trains[j],trains[j1]);}returnswaps;// 返回总交换次数}intmain(intargc,char*argv[]){// 加速输入输出cin.tie(0);cin.sync_with_stdio(false);intcases;// 测试用例个数cincases;while(cases--){intnumber;// 当前测试用例的车厢数量cinnumber;trains.clear();// 清空向量// 读取车厢序列intindex;for(inti1;inumber;i){cinindex;trains.push_back(index);}// 输出结果coutOptimal train swapping takes sortAndCount() swaps.\n;}return0;}// Train Swapping// UVa ID: 299// Verdict: Accepted// Submission Date: 2016-05-09// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;vectorinttrains;intcases,number;intsortAndCount(){intswaps0;for(inti1;inumber;i)for(intj0;jtrains.size();j)if(trains[j]i){swapsj;trains.erase(trains.begin()j);break;}returnswaps;}intmain(intargc,char*argv[]){cin.tie(0);cin.sync_with_stdio(false);cincases;while(cases--){cinnumber;trains.clear();intindex;for(inti1;inumber;i){cinindex;trains.push_back(index);}coutOptimal train swapping takes sortAndCount() swaps.\n;}return0;}总结本题的核心是识别出问题本质为求逆序对数因为相邻交换排序的最小次数等于逆序总数。理解了这一点后可以用多种方法求解。题目给出的L≤50L \leq 50L≤50的限制使得O(L2)O(L^2)O(L2)的算法完全足够无需使用更高效的归并排序或树状数组等O(LlogL)O(L \log L)O(LlogL)的方法。
