本来是做hdu2838的,但貌似涉及到逆序数这个概念,于是就学习了下,后来求逆序数可以用归并排序,也就顺带把这个排序学了下(其实早就该掌握的),搞acm真的是学无止境啊!
对于n个元素,一般规定有一个标准排列(貌似大部分都是以一个递增的排列为准)对于这n个元素如果与标准排列的先后顺序不同,就说有一个逆元,这个排列的所有逆元就叫逆序数。其是一般的题目都是求逆序数,怎么求呢, 对于5个元素 5 2 4 3 1 比5小的个数有4个,比2小的个数有1个,比4小的个数2个,比3小的个数有1个,比1小的个数有0个,所以逆序数的个数就是4+1+2+1+0=8,首先O(n^2)的算法都想得到,枚举每一个数开他后面有多少个数比他小,把这些数都加起来就行了,但是如果数据达到100000程序跑起来就有点吃力了,有没有更好的算法呢?有归并排序就是O(n*log(n))的算法。按我的理解就是把一个n序列分成n/2 个序列,再分成n/4个序列......直到把这个序列分成2,2一组,然后对这n/2组序列中的2个元素排序,然后就合并成n/4组序列再排序、、、、最后合并成一个序列也就是排好序的序列,其实合并与排序树同时进行的,先拆分再合并 说白了就是递归。
怎么求逆序数呢?也只要在排序的时候统计就行了。具体见代码。
#include<stdio.h>
#include<string.h>
#define N 100005
int a[N],ans,temp[N];
void merge_sort(int x,int mid,int y)
{
int i=x,j=mid+1,k=0;
while(i<=mid&&j<=y)
{
if(a[i]>a[j])
{
temp[k++]=a[j++];
ans+=mid-i+1;//因为序列里的数都是排好序的,所以当a[j]<a[i]是a[j]也会小于a[i+1]直到a[mid]所以有mid-i+1个数大于a[i]
}
else
temp[k++]=a[i++];
}
while(i<=mid) temp[k++]=a[i++];
while(j<=y) temp[k++]=a[j++];
for(i=0;i<k;i++)
a[x+i]=temp[i];
}
void merge(int x,int y)
{
if(x<y)
{
int mid=(x+y)/2;
merge(x,mid);
merge(mid+1,y);
merge_sort(x,mid,y);
}
}
int main()
{
int n,i,j;
while(~scanf("%d",&n))
{
ans=0;//记录逆序数
for(i=0;i<n;i++)
scanf("%d",&a[i]);
merge(0,n-1);//归并
printf("%d\n",ans);
}
return 0;
}
其实求逆序数还可以用树状数组,思想就不说了,贴一份代码
#include<stdio.h> #include<string.h> #define N 100005 int c[N],n,a[N]; int lowbit(int x) { return x&(-x); } void add(int x,int val) { while(x<=n) { c[x]+=val; x+=lowbit(x); } } int Sum(int x) { int sum=0; while(x) { sum+=c[x]; x-=lowbit(x); } return sum; } int main() { int i; while(~scanf("%d",&n)) { for(i=1;i<=n;i++) scanf("%d",&a[i]); long long ans=0; memset(c,0,sizeof(c)); for(i=1;i<=n;i++) { add(a[i],1); ans+=i-Sum(a[i]); } printf("%lld\n",ans); } return 0; }
最后就要讲一下我开始说的hdu的那个题
http://acm.hdu.edu.cn/showproblem.php?pid=2838
这题就是说给你一个序列,让你通过移动使得最终的序列为上升的一个序列,但每次移动只能移动相邻的2个数,并且移动的代价为移动的2个数的和,最后问你把这个序列变成上升的序列后代价最小。
Cow Sorting
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1986 Accepted Submission(s): 608
Please help Sherlock calculate the minimal time required to reorder the cows.
Lines 2..N + 1: Each line contains a single integer: line i + 1 describes the grumpiness of cow i.
#include<stdio.h> #include<string.h> #define N 100010 __int64 c[N],a[N],num[N],n; __int64 lowbit(__int64 x) { return x&(-x); } void add(__int64 x,__int64 val,__int64 index) { while(x<=n) { c[x]+=val; num[x]+=index; x+=lowbit(x); } } __int64 sum_a(__int64 x) { __int64 sum=0; while(x) { sum+=c[x]; x-=lowbit(x); } return sum; } __int64 sum_num(__int64 x) { __int64 sum=0; while(x) { sum+=num[x]; x-=lowbit(x); } return sum; } int main() { while(~scanf("%I64d",&n)){ int i,j; for(i=1;i<=n;i++) scanf("%I64d",&a[i]); memset(c,0,sizeof(c)); memset(num,0,sizeof(num)); __int64 ans=0,ret; for(i=1;i<=n;i++) { add(a[i],a[i],1); ret=sum_a(n)-sum_a(a[i]); ans+=(i-sum_num(a[i]))*a[i]+ret; } printf("%I64d\n",ans); } return 0; }