首页 > 代码库 > HDU 1394 Minimum Inversion Number.(线段树)
HDU 1394 Minimum Inversion Number.(线段树)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1394
~~~~
早起一发线段树,开心又快乐。这题暴力也能水过,同时线段树的效率也就体现的尤为明显了,看了大牛的博客,说是还可以用树状数组,点树和合并序列写,现在还不懂,留着以后在写吧。
~~~~
大致题意:给定一个数字序列,同时由此可以得到n个序列, 要求从n个序列中找到逆序数最小的序列,输出最小逆序数。
首先介绍下逆序数的概念:
在一个排列中,如果一对数的前后位置与大小顺序相反,即前面的数大于后面的数,那末它们就称为一个逆序。
一个排列中逆序的总数就称为这个排列的逆序数。逆序数为偶数的排列称为偶排列;逆序数为奇数的排列称为奇排列。
同时求解逆序数有个小公式:
a[0]后边有a[0]个比a[0]小的数(想想为什么),将a[0]移到末尾时,a[0]的逆序数变成n-1-a[0];
而a[0]个比a[0]小的数的逆序数都减1,设原序列的逆序数为sum,则新序列的逆序数sum=sum-a[0]+n-1-a[0];
~~~~
#include<cstdio> #include<algorithm> #include<cstring> #define lson rt<<1,s,mid #define rson rt<<1|1,mid+1,e #define N 5000+100 using namespace std; int tre[N<<2]; void pushup(int rt) { tre[rt]=tre[rt<<1]+tre[rt<<1|1]; } void build(int rt,int s,int e) { tre[rt]=0; if(s==e) return ; int mid=(s+e)>>1; build(lson); build(rson); } int query(int l,int r,int rt,int s,int e) { if(l==s && r==e) return tre[rt]; int mid=(s+e)>>1; if(r<=mid) return query(l,r,lson); else if(l>mid) return query(l,r,rson); else return query(l,mid,lson)+query(mid+1,r,rson); } void update(int pos,int rt,int s,int e) { if(s==e) { tre[rt]++; return ; } int mid=(s+e)>>1; if(pos<=mid) update(pos,lson); else update(pos,rson); pushup(rt); //更新。 } int n,a[N]; int main() { while(scanf("%d",&n)==1) { int tot=0; build(1,0,n-1); for(int i=0;i<n;i++) { scanf("%d",&a[i]); tot+=query(a[i],n-1,1,0,n-1); //线段树求解a[i]之前的逆序数。 update(a[i],1,0,n-1); //更新,也就是把a[i]压入线段树。 } //printf("%d\n",tot); int ans=tot; for(int i=0;i<n;i++) { tot=tot+(n-1-a[i])-a[i]; //相当于依次把第i个数放到a[0]的位置 ans=min(ans,tot); } printf("%d\n",ans); } return 0; }
~~~~
暴力解法。····
#include<cstdio> #include<algorithm> #include<cstring> #define N 5000+100 #define INF 0x3f3f3f3f using namespace std; int n; int a[N],b[N]; int qyj() { int tot=0; for(int i=0;i<n-1;i++) { for(int j=i+1;j<n;j++) { if(a[i]>a[j]) tot++; } } return tot; } int main() { while(scanf("%d",&n)==1) { for(int i=0;i<n;i++) scanf("%d",&a[i]); int tot=qyj(),ans=tot; for(int i=0;i<n;i++) { tot=tot+(n-1-a[i])-a[i]; ans=min(ans,tot); } printf("%d\n",ans); } return 520; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。