題目連結: https://zerojudge.tw/ShowProblem?problemid=b373
# 內容
在一个旧式的火车站旁边有一座桥，其桥面可以绕河中心的桥墩水平旋转。一个车站的职工发现桥的长度最多能容纳两节车厢，如果将桥旋转 180 度，则可以把相邻两节车厢的位置交换，用这种方法可以重新排列车厢的顺序。于是他就负责用这座桥将进站的车厢按车厢号从小到大排列。他退休后，火车站决定将这一工作自动化，其中一项重要的工作是编一个程序，输入初始的车厢顺序，计算最少用多少步就能将车厢排序。车厢编号从 1 开始。
其實，就是指說：給你一串數列，問最少交換幾次可以使號碼由小而大排好
# 思路
其實，它就是十分經典的問題之一喔～，稱作 – 逆序數對數量計算 (以後就可以用 BIT 取代)
對於一個陣列 A 中，任取兩個元素，順序不變，如果前者大於後者， 則我們稱為逆序數對
其解決方法有三，一為暴力法，二為分治法，三為 BIT 解法，在這就先用分治法吧
經過觀察會發現:
- 即使將左右兩部分排序，這部分的數量依然相同～～(廢話)~~
![]()
- 經過排序以後窮舉左邊的每一項，與它有關的逆序數對是原本右邊滿足的部分，加上往右找比它小的那些數值
# 作法
- 以合併排序法為基礎
- 在合併前額外加上計算 “橫跨左右部分的逆序數對數量”
- 回傳三個部份的總和，就是在處理範圍中的逆序數對數量
- 順便也幫忙排序完成了！
在此問題中，子問題的答案並不只有「該區間內逆序數對的數量」，也隱含了「該區間內排序過的結果」
# 程式碼
#include<bits/stdc++.h> | |
using namespace std; | |
#define N 1000005 | |
#define int long long | |
int data[N],tmp[N]; | |
int mergecount(int L,int R){ | |
if(L+1==R) return 0; // 僅有單一元素 | |
int count=0,M=(R-L)/2+L; | |
count+=mergecount(L,M); // 左 | |
count+=mergecount(M,R); // 右 | |
int a=L,b=M,k=L,t=M-1; | |
for(int i=L,i<M;i++){ | |
while(t+1<R&&data[i]>data[t+1]) t++; | |
count+=t-M+1; | |
} | |
/* 順便合併排序 */ | |
while(a<M||b<R){ | |
if(a<M&&(b>=R||data[a]<data[b])){ | |
tmp[k++]=data[a++]; | |
}else{ | |
tmp[k++]=data[b++]; | |
} | |
} | |
for(int i=L,i<R,i++) // 儲存合併排序的結果 | |
data[i]=tmp[i]; | |
return count; | |
} | |
int main(){ | |
ios::sync_with_stdio(false); | |
cin.tie(); | |
int n,ans,t=1; | |
while(cin>>n&&n){ | |
for(int i=0;i<n;i++) | |
cin>>data[i]; | |
ans=mergecount(0,n); | |
cout<<ans; | |
} | |
return 0; | |
} |
