1203: 逆序數

Time Limit:?1 Sec??Memory Limit:?128 MB
Submit:?569??Solved:?119
[Submit][Status][Web Board]

Description

在一個排列中，如果一對數的前后位置與大小順序相反，即前面的數不小于后面的數，那么它們就稱為一個逆序。一個排列中逆序的總數就稱為這個排列的逆序數。

如2 4 3 1中，2 1，4 3，4 1，3 1是逆序，逆序數是4。給出一個整數序列，求該序列的逆序數。

?

Input

多組測試數據

每組測試數據分兩行，第一行一個正整數n（n?<=?50000)

第二行有n個元素(?0?<=?A[i]?<=?10^9)

?

Output

每組測試數據輸出一行表示逆序數

?

Sample Input

4

2 4 3 1

3

1 1 1

Sample Output

4

3

HINT

?

Source

?

[Submit][Status][Web Board]

中文??English??
Anything about the Problems, Please Contact Admin:admin?
All Copyright Reserved 2010-2011?ZCMU?TEAM

#include<bits/stdc++.h> using namespace std;#define e exp(1) #define pi acos(-1) #define mod 1000000007 #define inf 0x3f3f3f3f #define ull unsigned long long #define ll long longconst int maxn = 3e6+200; int ans; int a[maxn],temp[maxn]; void merge(int l,int mid,int r) {int i=l;int j=mid+1;int k=l;while(i<=mid&&j<=r){if(a[j]>a[i]){temp[k++]=a[i++];}else{ans+=mid-i+1;temp[k++]=a[j++];}}while(i<=mid)temp[k++]=a[i++];while(j<=r)temp[k++]=a[j++];for(i=l;i<=r;i++)a[i]=temp[i]; } void merge_sort(int x,int y) {if(x>=y)return ;int t=x+y>>1;merge_sort(x,t);merge_sort(t+1,y);merge(x,t,y); } int main() {int n;while(~scanf("%d",&n)){for(int i=0;i<n;i++)scanf("%d",&a[i]);ans=0;merge_sort(0,n-1);printf("%d\n",ans);}}

?

總結

以上是生活随笔為你收集整理的zcmu1203（逆序对，归并排序）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。