hdu1394 （逆序数，暴力，线段树）

点击打开链接

一直没理解题目什么意思，后来看网上的解释才明白。

1,暴力解法

给你一个有0-n-1组成的序列。这个序列有n-1中排列方式（题中所给的），让你求出那种排列的逆序数最小。

n-1中排列中，每次都把最前面的a[i]放在序列最后面。此时关键就来了，当a[i]在最前面时，后面一定有a[i]个比他小的数，n-a[i]-1个比a[i]大的数，所以每次把a【i】移到最后时，逆序数就会变化,a[i]到最后时，对应a[i]的逆序数为n-a[i]-1-a[i].

所以先求出原来序列的总逆序数sum，然后遍历，每次都更新总序列的逆序数，即sum= sum + n- a [ i ] -1 -a [ i ].

#include"stdio.h"
#include"string.h"
#define N 5004
int main()
{
int n;
int ans;
int min;
int a[N];
int i,j;
while(scanf("%d",&n)!=-1)
{
for(i=0;i<n;i++)
scanf("%d",&a[i]);
ans=0;
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
if(a[i]>a[j])ans++;
}
min=ans;
for(i=0;i<n-1;i++)
{
ans=ans-a[i]+(n-a[i]-1);
if(min>ans)
min=ans;
}
printf("%dn",min);
}
return 0;
}

2，线段树。

因为线段树直接就是有序的查找数据，所以要求a[i]对应的逆序数，只需要find(a【i】+1,n,1)就可以了。

主一要处理0的情况。。

#include"stdio.h"
#include"string.h"
#define N 5004
struct node
{
int x,y,mid,sum;
}A[N*3];
void build(int x,int y,int t)
{
A[t].x=x;
A[t].y=y;
A[t].mid=(x+y)/2;
A[t].sum=0;
if(x==y)return ;
build(x,A[t].mid,t*2);
build(A[t].mid+1,y,2*t+1);
return ;
}
void insert(int x,int t)
{
if(A[t].x==A[t].y&&A[t].x==x)
{
A[t].sum=1;
return ;
}
if(x<=A[t].mid)
insert(x,2*t);
else
insert(x,2*t+1);
A[t].sum=A[2*t].sum+A[2*t+1].sum;
return ;
}
int find(int x,int y,int t)
{
int sum;
sum=0;
if(A[t].x==x&&A[t].y==y)
return A[t].sum;
if(y<=A[t].mid)
sum+=find(x,y,2*t);
else if(x>A[t].mid)
sum+=find(x,y,2*t+1);
else
{
sum+=find(x,A[t].mid,2*t);
sum+=find(A[t].mid+1,y,2*t+1);
}
return sum;
}
int main()
{
int a[N];
int i,n;
while(scanf("%d",&n)!=-1)
{
build(1,n,1);
int sum=0;
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
a[i]++;//避免0的出现
if(a[i]+1<=n)
sum+=find(a[i]+1,n,1);
insert(a[i],1);
}
int ans=99999999;
for(i=1;i<=n;i++)
{
sum=sum+n-(a[i]-1)-1-(a[i]-1);
if(ans>sum)ans=sum;
}
printf("%dn",ans);
}
return 0;
}

最后

以上就是可爱乌龟最近收集整理的关于hdu1394 （逆序数，暴力，线段树）的全部内容，更多相关hdu1394内容请搜索靠谱客的其他文章。