hdu 1394——Minimum Inversion Number

本文主要是介绍hdu 1394——Minimum Inversion Number，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

线段树

//31MS 340K c++
#include<iostream>
#include<cstdio>
using namespace std;
#define maxn 5010
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid ((t[rt].l+t[rt].r)>>1)
struct tree
{int l,r;int sum;
}t[maxn<<4];
int num[maxn];
void pushup(int rt)
{t[rt].sum=t[ls].sum+t[rs].sum;
}
void build(int rt,int l,int r)
{t[rt].l=l,t[rt].r=r,t[rt].sum=0;if(l==r)return ;build(ls,l,mid);build(rs,mid+1,r);
}
void add(int rt,int x)
{if(t[rt].l==t[rt].r){t[rt].sum=1;return ;}if(x<=mid)add(ls,x);elseadd(rs,x);pushup(rt);
}
int query(int rt,int l,int r)
{if(t[rt].l==l&&t[rt].r==r)return t[rt].sum;if(r<=mid)return query(ls,l,r);elseif(l>mid)return query(rs,l,r);elsereturn query(ls,l,mid)+query(rs,mid+1,r);
}
int main()
{int n;while(~scanf("%d",&n)){build(1,0,n-1);int sum=0;for(int i=0;i<n;i++){scanf("%d",&num[i]);sum+=query(1,num[i],n-1);add(1,num[i]);		}int ans=sum;for(int i=0;i<n-1;i++){sum+=n-1-2*num[i];ans=min(ans,sum);}	printf("%d\n",ans);}return 0;
}

 

树状数组

//15MS 308K  c++
#include<cstdio>
#include<iostream>
using namespace std;
#define maxn 5010
int num[maxn];
int t[maxn];
int n;
int lowbit(int x)
{return (-x)&x;
}
int Sum(int x)
{int sum=0;while(x>=1)	{sum+=t[x];x-=lowbit(x);}return sum;
}
void Update(int x)
{while(x<=n){t[x]++;x+=lowbit(x);}
}
int main()
{while(~scanf("%d",&n)){memset(t,0,sizeof(t));int sum=0;for(int i=0;i<n;i++){scanf("%d",&num[i]);sum+=Sum(n)-Sum(num[i]+1);Update(num[i]+1);}int ans=sum;for(int i=0;i<n-1;i++){sum+=n-1-2*num[i];ans=min(sum,ans);}printf("%d\n",ans);}return 0;
}

 

这篇关于hdu 1394——Minimum Inversion Number的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---