首页 > 代码库 > HDU 1394 Minimum Inversion Number（线段树求逆序对）

HDU 1394 Minimum Inversion Number（线段树求逆序对）

2024-07-12 11:23:11   218人阅读

题目链接：　　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 }
View Code


联系
我们