首页 > 代码库 > HDU 1394——Minimum Inversion Number(最小逆序数)
HDU 1394——Minimum Inversion Number(最小逆序数)
题意:
给定一个序列,里面的数是0到n-1, 每次要把第一个数放到最后一个数,重复n次,求n次操作中最小的逆序数是多少?
思路:
先求出初始的逆序数,然后每移动第一个数到最后面,那么逆序数要减去比它小的数的个数,加上比它大的数的个数。 如果我输入的数是a[i],那么比它小的数的个数就有a[i]个,比它大的数的个数就有n-1-a[i]个
方法: 归并排序 ,树状数组,线段树
归并排序代码:
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #define inf 0x3f3f3f3f #define M 5001 using namespace std; int ans,n; int a[M],t[M],b[M]; void merge_sort(int *A,int x,int y,int *T) { if(y-x>1){ int m=(y+x)>>1; int p=x,q=m,i=x; merge_sort(A,x,m,T); merge_sort(A,m,y,T); while(p<m||q<y){ if(q>=y||(p<m&&A[p]<=A[q])) T[i++]=A[p++]; else {T[i++]=A[q++];ans+=m-p;} } for(i=x;i<y;++i){ A[i]=T[i]; } } } int main() { //freopen("input.txt","r",stdin); while(scanf("%d",&n)!=EOF){ ans=0; for(int i=0;i<n;++i){ scanf("%d",&a[i]); b[i]=a[i]; <span style="white-space:pre"> </span> } merge_sort(b,0,n,t); <span style="white-space:pre"> </span>//用临时数组排序求逆序数,因为我们还要引用原数组的数, int minn=ans; for(int i=0;i<n;++i){ ans+=n-1-2*a[i]; minn=min(minn,ans); } cout<<minn<<endl; } return 0; }
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #define inf 0x3f3f3f3f #define M 5001 using namespace std; int c[M],a[M],n; int lowbit(int x) { return x&-x; } void update(int x,int v) { while(x<=n){ c[x]+=v; x+=lowbit(x); } } int get_sum(int x) { int ans=0; while(x>0){ ans+=c[x]; x-=lowbit(x); } return ans; } int main() { //freopen("input.txt","r",stdin); while(scanf("%d",&n)!=EOF){ memset(c,0,sizeof c); int ans=0; for(int i=0;i<n;++i){ scanf("%d",&a[i]); ans+=get_sum(n)-get_sum(a[i]+1); <span style="white-space:pre"> </span>//求比a[i]大的个数 update(a[i]+1,1); } //cout<<ans<<endl; int minn=inf; for(int i=0;i<n;++i){ ans+=n-1-2*a[i]; minn=min(minn,ans); } cout<<minn<<endl; } return 0; }
线段树代码:
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #define M 5001 #define ls(x) x<<1 #define rs(x) x<<1|1 using namespace std; int n; int a[M]; struct node { int l,r,num; }tre[4*M]; void push_up(int rt) { tre[rt].num=tre[ls(rt)].num+tre[rs(rt)].num; } void build(int rt,int l,int r) { tre[rt].l=l; tre[rt].r=r; tre[rt].num=0; if(l==r) return; int m=(l+r)>>1; build(ls(rt),l,m); build(rs(rt),m+1,r); push_up(rt); } void update(int rt,int p,int v) { if(tre[rt].l==tre[rt].r){ tre[rt].num=v; return; } int m=(tre[rt].l+tre[rt].r)>>1; if(p<=m) update(ls(rt),p,v); else update(rs(rt),p,v); push_up(rt); } int get_sum(int rt,int l,int r) { if(l<=tre[rt].l&&tre[rt].r<=r){ return tre[rt].num; } int sum=0; int m=(tre[rt].l+tre[rt].r)>>1; if(l<=m) sum+=get_sum(ls(rt),l,r); if(m<r) sum+=get_sum(rs(rt),l,r); return sum; } int main() { //freopen("input.txt","r",stdin); while(scanf("%d",&n)!=EOF){ build(1,0,n-1); int ans=0; for(int i=0;i<n;++i){ scanf("%d",&a[i]); ans+=get_sum(1,a[i]+1,n-1); //求比a[i]大的数的个数 update(1,a[i],1); } int minn=ans; for(int i=0;i<n;++i){ ans+=n-1-2*a[i]; minn=min(minn,ans); } cout<<minn<<endl; } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。