題目描述

• 給定一個長度為n的整數數列，請你計算數列中的逆序對的數量。
• 逆序對的定義如下：對于數列的第i個和第j個元素，如果滿足i<j且a[i]>a[j]，則其為一個逆序對；否則不是。
• 輸入格式：
  • 第一行包含整數n，表示數列的長度。
  • 第二行包含n個整數，表示整個數列。
• 輸出格式：
  • 輸出一個整數，表示逆序對的個數。
• 數據范圍：
  • 1≤n≤100000，
  • 數列中的元素的取值范圍[1,10的9次方]。

解題代碼（蠻力版）

起初解題的基本思路是：每次從序列中按照順序取出一個元素，然后逐一比較該元素與其后方的每一個元素是否構成逆序對。這種算法是一種平方時間復雜度的算法，實現代碼如下所示：

#include<cstdio>
using namespace std;const int N = 1e6 + 10;
int a[N];
int n;
int count(0);int main(void)
{scanf("%d",&n);for(int i(0);i<n;++i) scanf("%d",&a[i]);for(int i(0); i < n - 1; ++i)for(int j(i+1); j < n; ++j)if(a[i] > a[j]) count++;printf("%d",count);return 0;
}

上述代碼在輸入的數據量很大時運行超時，因此需要時間復雜度更低的算法。

解題代碼（基于歸并排序）

基于歸并排序的解題代碼如下：

#include<cstdio>
using namespace std;const int N(1e5 + 10);
int a[N];
int n;
int temp[N];typedef long long LL;LL merge_sort(int* a, const int& left, const int& right)
{if(left >= right) return 0;const int mid((left + right) >> 1);int i(left), j(mid + 1), k(0);LL count = (merge_sort(a, left, mid) + merge_sort(a, mid + 1, right));while(i <= mid && j <= right){if(a[i] <= a[j]) temp[k++] = a[i++];else{temp[k++] = a[j++];count += (mid - i + 1);}}while(i <= mid) temp[k++] = a[i++];while(j <= right) temp[k++] = a[j++];for(int i(0), j(left); j <= right;) a[j++] = temp[i++];return count;
}int main(void)
{scanf("%d",&n);for(int i(0); i < n; ++i) scanf("%d",&a[i]);printf("%lld",merge_sort(a, 0, n-1));return 0;
}

注意事項：

• long long數據類型的使用：上述代碼中使用了long long這種數據類型，這是考慮到如果使用int會超出范圍所致，分析如下：
  • 一個長度為n的序列最多含有n(n-1)/2個逆序對，當n很大時，大致為n2/2。當n的取值為題目中的上限100000時，則最多有50億個逆序對，超過了int的表示范圍（21億多），因此需要使用比int表示范圍更大的整數類型。
  • 比int類型表示范圍更大的整數類型有兩種，分別是long和long long。int占用四個字節，但是，long可能占有四個字節可能占用八個字節，因此其表示范圍不一定比int更大，所以需要使用一定占用八個字節的long long數據類型。
  • 代碼中，習慣使用typedef long long LL為long long類型進行重命名。
• 計算前后段逆序對的時間：注意需要在歸并排序之前就計算原始序列的兩段子序列逆序對，而不是在代碼最后完成歸并排序了再進行計算，這樣會導致計算結果不同。