首页 > 代码库 > HDU 1394 Minimum Inversion Number(线段树求逆序对)
HDU 1394 Minimum Inversion Number(线段树求逆序对)
题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=1394
解题报告:给出一个序列,求出这个序列的逆序数,然后依次将第一个数移动到最后一位,求在这个过程中,逆序数最小的序列的逆序数是多少?
这题有一个好处是输入的序列保证是0 到 n-1,所以不许要离散化,还有一个好处就是在计算在这个序列中比每个数大和小的数一共有多少个的时候可以在O(1)时间计算出来,一开始我没有意识到,还傻傻的用了两层for循环来每次都计算,当然这样果断TLE了。把一个数从第一个移动到最后一个的时候逆序数的变化就等于原来的逆序数加上这个序列中所有比这个数大的数的个数再减去所有比这个数小的个数。
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 using namespace std; 6 const int maxn = 5000+5; 7 int que[maxn]; 8 struct node 9 {10 int data,l,r;11 }tree[2*maxn];12 void maketree(int p)13 {14 if(tree[p].l == tree[p].r)15 return ;16 int mid = (tree[p].l + tree[p].r) / 2;17 tree[2*p].data = http://www.mamicode.com/0;18 tree[2*p].l = tree[p].l;19 tree[2*p].r = mid;20 maketree(2*p);21 tree[2*p+1].data = http://www.mamicode.com/0;22 tree[2*p+1].l = mid + 1;23 tree[2*p+1].r = tree[p].r;24 maketree(2*p+1);25 }26 int find(int p,int l,int r)27 {28 if(l > r)29 return 0;30 if(tree[p].l == l && tree[p].r == r)31 return tree[p].data;32 int mid = (tree[p].l + tree[p].r) / 2;33 if(r <= mid)34 return find(2*p,l,r);35 if(l <= mid && r > mid)36 return find(2*p,l,mid) + find(2*p+1,mid +1,r);37 else return find(2*p+1,l,r);38 }39 void push(int p,int d)40 {41 tree[p].data++;42 if(tree[p].l == tree[p].r)43 return ;44 int mid = (tree[p].l + tree[p].r) / 2;45 if(d <= mid)46 push(2*p,d);47 else push(2*p+1,d);48 }49 int main()50 {51 int n;52 while(scanf("%d",&n)!=EOF)53 {54 for(int i = 0;i < n;++i)55 scanf("%d",&que[i]);56 tree[1].data = http://www.mamicode.com/0;57 tree[1].l = 0;58 tree[1].r = n-1;59 maketree(1);60 int tot = 0;61 for(int i = 0;i < n;++i)62 {63 tot += find(1,que[i] + 1,n-1);64 push(1,que[i]);65 }66 int ans = tot;67 for(int i = 0;i < n;++i)68 {69 tot = tot - que[i] + n - que[i] - 1;70 ans = min(tot,ans);71 }72 printf("%d\n",ans);73 }74 return 0;75 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。