【算法】788.逆序对的数量

题目

逆序对的数量

思路

在归并排序的基础上求逆序数，如果l-mid中的数大于mid+1-r中的数，则i和i之后的所有数都是指针j所指数的逆序数。与归并算法不同的是，本题需要有返回值，返回逆序数的数量。

代码 #include<iostream> using namespace std; typedef long long ll; const int N = 100010; int n; int a[N], temp[N]; ll merge_sort(int l, int r) { if (l >= r) { return 0; } int mid = (l + r) / 2; ll sum=merge_sort(l, mid)+merge_sort(mid + 1, r); int k = 0, i = l, j = mid + 1; while (i <= mid && j <= r) { if (a[i] <= a[j]) { temp[k++] = a[i++]; } else { temp[k++] = a[j++]; sum = sum + mid - i + 1; } } while (i <= mid) { temp[k++] = a[i++]; } while (j <= r) { temp[k++] = a[j++]; } for (int i = l, j = 0;i <= r;i++, j++) { a[i] = temp[j]; } return sum; } int main() { cin >> n; for (int i = 0;i < n;i++) { cin >> a[i]; } cout << merge_sort(0, n - 1) << endl; return 0; }