首页 > 代码库 > hdu 1394 Minimum Inversion Number（线段树or树状数组）
hdu 1394 Minimum Inversion Number（线段树or树状数组）
题意：
给你N个数，N个数是0~N-1的一个全排列。
要求统计它的所有形式的逆序对的最小值。它的所有形式的意思是，不断将数组开头的第一个数放到数组的最后面。
逆序对：i<j且ai>aj
思路：
树状数组也可以，，
看代码
代码：
const int maxn = 50005;int sum[maxn<<2];int n;void PushUp(int rt){ sum[rt] = sum[rt<<1] + sum[rt<<1|1];}void build(int l,int r,int rt){ sum[rt] = 0; if(l==r) return; int m = (l + r) >> 1; build(lson); build(rson);}void update(int p,int l,int r,int rt){ if(l==r){ ++sum[rt]; return; } int m = (l + r) >> 1; if(p <= m) update(p,lson); else update(p,rson); PushUp(rt);}int query(int L,int R,int l,int r,int rt){ if(L<=l && r<=R){ return sum[rt]; } int m = (l + r) >> 1; int ret = 0; if(L <= m) ret += query(L,R,lson); if(R > m) ret += query(L,R,rson); return ret;}int main(){ int a[maxn]; while(scanf("%d",&n)!=EOF){ build(0,n-1,1); int sum = 0; for(int i=1;i<=n;++i){ scanf("%d",&a[i]); sum += query(a[i]+1,n-1,0,n-1,1); update(a[i],0,n-1,1); } //printf("%d\n",sum); int ans = sum; for(int i=1;i<n;++i){ sum += ( n - a[i] -1 - a[i] ); ans = min( ans,sum ); } printf("%d\n",ans); }}
hdu 1394 Minimum Inversion Number（线段树or树状数组）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。