51Nod 求逆序数 树状数组 + 离散化
本文共 2350 字，大约阅读时间需要 7 分钟。
基准时间限制：1 秒 空间限制：131072 KB 分值: 0
收藏 
关注 在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。
如2 4 3 1中，2 1，4 3，4 1，3 1是逆序，逆序数是4。给出一个整数序列，求该序列的逆序数。
Input
第1行：N，N为序列的长度（n <= 50000)第2 - N + 1行：序列中的元素（0 <= A[i] <= 10^9）
Output
输出逆序数
Input示例
42431
Output示例
4
方法1：归并排序
#include#define maxsize 50010long long int count = 0;int a[maxsize],temp[maxsize]; void merge(int s,int m,int e) { int p1 = s,p2 = m+1,p = 0; while(p1 <= m && p2 <= e) { if(a[p1]<=a[p2]) temp[p++]=a[p1++]; else { temp[p++]=a[p2++]; count += m-p1+1; } } while(p1<=m) temp[p++]=a[p1++]; while(p2<=e) temp[p++]=a[p2++]; int i; for(i = 0;i < p; ++i) a[s+i] = temp[i]; } void mergesort(int l,int r) { if(l
方法二：树状数组 + 离散化
离散化参考：
树状数组：
树状数组求逆序原理：
#includeusing namespace std;const int MAXN = 50005;int C[MAXN];int a[MAXN];int n;struct Node{ int d,ord;//数据与 位置 bool operator<(const Node o)const{ return d < o.d; }}p[MAXN];int lowBit(int i){ return i&(-i);}int add(int i,int x){ while(i <= n){ C[i] += x; i += lowBit(i); }}int getSum(int i){ int sum = 0; while(i){ sum += C[i]; i -= lowBit(i); } return sum;}int main() { scanf("%d",&n); memset(C,0,sizeof(C)); for(int i = 1; i <= n; ++i){//从1开始 scanf("%d",&p[i].d); p[i].ord = i; } sort(p+1,p+n+1);//按照数据大小 从小到大排序 //数据被离散化为从1开始的数 for(int i = 1; i <= n; ++i){ a[p[i].ord] = i; } int ans = 0; for(int i = 1; i <= n; ++i){ add(a[i],1);//a[i]表示新的数据 ans += i - getSum(a[i]); //这里 i可以用getSum(n)代替 i表示当前共有多少数 减去比a[i]小的数 } printf("%d\n",ans); return 0; }
在数据范围比较小的情况下，可以不用离散化
但是需要注意，数据不能有 0 值，若有0可以对每个数据加一的方式或者进行离散化 原因:0&0 == 0 此时无法实现i的更新 会进入死循环（add中的while）
#includeusing namespace std;const int MAXN = 50000;int C[MAXN];int n;int lowBit(int i){ return i&(-i);}int add(int i, int x){ while(i <= n){ C[i] += x; i += lowBit(i); }}int getSum(int i){ int sum = 0; while(i > 0){ sum += C[i]; i -= lowBit(i); } return sum;}int main() { memset(C,0,sizeof(C)); scanf("%d",&n); int x; int ans = 0; for(int i = 1; i <= n; ++i){ scanf("%d",&x); add(x,1); ans += i - getSum(x); } printf("%d\n",ans);// for(int i = 1; i <= n; ++i){// printf("%d ",C[i]);// } //cout << getSum(5)-getSum(3); return 0; }
转载地址：http://neimi.baihongyu.com/
你可能感兴趣的文章
中断API之__tasklet_schedule
查看>>
中断API之enable_irq
查看>>
中断API之disable_irq
查看>>
nova 中的guestfs
查看>>
nova中的localfs
查看>>
utils/rpm_build.sh
查看>>
查看模块参数
查看>>
udev重命名网口
查看>>
pgrep
查看>>
test-definitions/blob/master/toolset/util/parallel_cmds.py
查看>>
中断API之irq_activate
查看>>
中断API之tasklet_disable_nosync/tasklet_trylock/tasklet_unlock
查看>>
中断API之tasklet_init/tasklet_kill
查看>>
内存管理API之__free_pages
查看>>
内存管理API之__get_free_pages
查看>>
内存管理API之__get_vm_area
查看>>
内存管理API之krealloc
查看>>
内存管理API之ksize
查看>>
内存管理API之alloc_pages
查看>>
linux performance tool
查看>>