本帖最後由 amoshuangyc 於 2014-8-9 22:28 編輯
這裡給出 merge sort 的解法。
考慮 merge 的過程:
左邊陣列中要比較的值為 A
右邊陣列中要比較的值為 B
當 B < A 時,必需將 B 左移到 A 之前,這時 B 左移時所越過的所有值都比 B 大。也就是說,B 與它所越過的值形成逆序數對,也就是題目要求的東西。
左移的過程就是 B 從右至左依序交換那些數。
越過的值的個數 就是 逆序數對數。
以下圖舉例:
6 得與 12, 11, 7 交換。注意,此時 1, 3, 2 已經排好了,也就是說 1, 3, 2 已經不在待比較的陣列中,已經被移到 結果陣列中了,所以我們不須考慮這三個數。
逆序數對:(12, 6), (11, 6), (7, 6)。
從上圖可以得知,得與 (m - idx_L + 1) 個 數交換。
完整 code :[C++] 純文本查看 復制代碼 #include <iostream>
using namespace std;
int data[2000000+1];
int temp[2000000+1];
long long merge(int p, int m, int q)
{
int idx_L = p;
int idx_R = m + 1;
int idx_temp = p;
long long cnt = 0;
while (idx_L <= m && idx_R <= q) {
if (data[idx_L] <= data[idx_R]) {
temp[idx_temp++] = data[idx_L++];
}
else {
temp[idx_temp++] = data[idx_R++];
cnt += (m - idx_L + 1); // 記算逆序數對數
}
}
while (idx_L <= m)
temp[idx_temp++] = data[idx_L++];
while (idx_R <= q)
temp[idx_temp++] = data[idx_R++];
for (int i=p; i<=q; i++)
data[i] = temp[i];
return cnt;
}
long long merge_sort(const int p, const int q)
{
if (p >= q) return 0;
int m = (p+q) / 2;
long long cnt_L = merge_sort(p, m);
long long cnt_R = merge_sort(m+1, q);
long long cnt_M = merge(p, m, q);
return (cnt_L + cnt_R + cnt_M);
}
int main()
{
int N;
cin >> N;
for (int i=0; i<N; i++)
cin >> data;
long long cnt = merge_sort(0, N-1);
cout << cnt << endl;
return 0;
}
|