NYOJ 117 求逆序数

求逆序数

时间限制：2000 ms  |  内存限制：65535 KB 难度：5 描述

在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。

现在，给你一个N个元素的序列，请你判断出它的逆序数是多少。

比如 1 3 2 的逆序数就是1。

输入

第一行输入一个整数T表示测试数据的组数（1<=T<=5)
每组测试数据的每一行是一个整数N表示数列中共有N个元素（2〈=N〈=1000000）
随后的一行共有N个整数Ai(0<=Ai<1000000000)，表示数列中的所有元素。

数据保证在多组测试数据中，多于10万个数的测试数据最多只有一组。

输出

输出该数列的逆序数

样例输入

2 2 1 1 3 1 3 2

样例输出

0 1

树状数组！

AC码：

// 离散化只能求没有重复的一组数的逆序对数 #include<stdio.h> #include<stdlib.h> #include<string.h> #define N 1000005 struct node {long long val,order; }num[N]; // 存储输入的原数组 long long a[N]; // 存储离散后的数据 long long c[N]; // 存树状数组 long long n; long long lowbit(long long x) {return x&(-x); } void update(long long x,long long t) {while(x<=n){c[x]+=t;x+=lowbit(x);} } long long getsum(long long x) {long long temp=0;while(x>=1){temp+=c[x];x-=lowbit(x);}return temp; } int cmp(const void *a,const void *b) {return (((struct node *)a)->val-((struct node *)b)->val); } int main() {long long T,i,ans,count;scanf("%lld",&T);while(T--){scanf("%lld",&n);for(i=1;i<=n;i++) // 输入的原数组{scanf("%lld",&num[i].val);num[i].order=i;}qsort(num+1,n,sizeof(num[1]),cmp);// 离散化count=0;num[i-1].val=0;for(i=1;i<=n;i++){if(num[i].val==num[i-1].val) // 去重a[num[i].order]=count;elsea[num[i].order]=++count;}// 用树状数组求逆序数memset(c,0,sizeof(c));ans=0;for(i=1;i<=n;i++){update(a[i],1);ans+=i-getsum(a[i]);}printf("%lld\n",ans);}return 0; }

总结

以上是生活随笔为你收集整理的NYOJ 117 求逆序数的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。