Description

對于數(shù)列a1,a2,a3…中的任意兩個(gè)數(shù)ai,aj (i < j)，如果ai > aj,那么我們就說這兩個(gè)數(shù)構(gòu)成了一個(gè)逆序?qū)?#xff1b;在一個(gè)數(shù)列中逆序?qū)Φ目倲?shù)稱之為逆序數(shù)，如數(shù)列 1 6 3 7 2 4 9中，(6,4)是一個(gè)逆序?qū)?#xff0c;同樣還有(3,2),(7,4),(6,2)，(6,3)等等，你的任務(wù)是對給定的數(shù)列求出數(shù)列的逆序數(shù)。
Input

輸入數(shù)據(jù)N(N <= 100000)表示數(shù)列中元素的個(gè)數(shù)，隨后輸入N個(gè)正整數(shù)，數(shù)字間以空格間隔。

Output

輸出逆序數(shù)。
Sample
Input

10 10 9 8 7 6 5 4 3 2 1

Output

45 #include<bits/stdc++.h>#define ll long longusing namespace std;const int N = 1e5 + 10; int a[N], temp[N]; ll sum; void merage(int left, int right) {int mid = (left + right) / 2;int i = left, j = mid + 1, k = 0;while(i <= mid && j <= right){if(a[i] <= a[j])temp[k++] = a[i++];else{temp[k++] = a[j++];sum += (mid - i + 1);}}while(i <= mid)temp[k++] = a[i++];while(j <= right)temp[k++] = a[j++];for(i = 0, j = left; i < k; i++, j++)a[j] = temp[i]; } void meragesort(int left, int right) {if(left < right){int mid = (left + right) / 2;meragesort(left, mid);meragesort(mid + 1, right);merage(left, right);} } int main() {ios::sync_with_stdio(0);int n;cin >> n;for(int i = 0; i < n; i++)cin >> a[i];sum = 0;meragesort(0, n - 1);cout << sum << endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的E - 数据结构实验之排序五：归并求逆序数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。