【SGU】180. Inversions（归并排序求逆序数）

本文主要是介绍【SGU】180. Inversions（归并排序求逆序数），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

以前一般用树状数组和线段树做这种题

这次换个思路试试，归并排序！

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn = 111111;
int n;
int array[maxn];
int tmp[maxn];
LL  ans;
void my_sort(int l,int r){if(l == r) return;int mid = (l + r) >> 1;my_sort(l,mid);my_sort(mid + 1,r);int cnt = 0,i,j;for(i = l,j = mid + 1;i <= mid && j <= r;){if(array[i] <= array[j]){tmp[cnt++] = array[i++];ans += (j - mid - 1);}elsetmp[cnt++] = array[j++];}while(i <= mid){tmp[cnt++] = array[i++];ans += (j - mid - 1);}while(j <= r){tmp[cnt++] = array[j++];}for(int i = 0,j = l; i < cnt; i++,j++)array[j] = tmp[i];
}
int main(){while(scanf("%d",&n) != EOF){ans = 0;for(int i = 0; i < n; i++)scanf("%d",&array[i]);my_sort(0,n - 1);
//        for(int i = 0; i < n; i++)
//            printf("%d ",array[i]);
//        puts("");printf("%I64d\n",ans);}return 0;
}

这篇关于【SGU】180. Inversions（归并排序求逆序数）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---