hdu 1394 Minimum Inversion Number(线段树求最小逆序数)-白红宇

hdu 1394 Minimum Inversion Number(线段树求最小逆序数)

阅读量：4205 次

发布时间：2019-05-26

本文共 2176 字，大约阅读时间需要 7 分钟。

题目链接:

题目大意: 给出N个数，这些数可以把后面的删掉然后放到最前面形成新的序列

可得到的N种情况，求出这N种情况哪种的逆序数最小

解题思路: 先求出第一个序列的逆序数，然后用很巧妙的办法求下一个序列的逆序数，直到全部求出

序列 4 5 2 1 3 6 ，此序列的逆序数为7，它等到的下一个序列为 5 2 1 3 6 4

看这个新序列的产生过程，首部删除4，尾部添加4

删除4，必然会使得这个序列的逆序数减少(4-1)个，因为4前面必定有4-1个数小于4

添加4，必然会使得这个序列的逆序数增加(6-4)个，因为4后面必定有6-4个数大于4

由此推出公式，假设移动的数为m，序列的逆序数=上一序列逆序数-(m-1)+(N-m)

由于给出的序列不是顺序的，所以先要离散化出来

[cpp]
 // 线段树  
 #include <stdio.h>  
 #include <string.h>  
 #include <stdlib.h>  
 #include <algorithm>  
 using namespace std;  
 #define MAX 5100  
 #define INF 0x3f3f3f3f  
 #define MID(a,b) (a+b)>>1  
 #define R(a) (a<<1|1)  
 #define L(a) a<<1  
 typedef struct {  
     int num,left,right;  
 }Node;  
 typedef struct {  
     int num,y;  
 }Nodes;  
 Nodes ans[MAX];  
 Node Tree[MAX<<2];  
 int n;  
   
 bool cmp(Nodes a,Nodes b)  
 {  
     return a.num>b.num?0:1;  
 }  
   
 bool cmp2(Nodes a,Nodes b)  
 {  
     return a.y>b.y?0:1;  
 }  
   
 void Build(int t,int l,int r)         //以1为根节点建立线段树    
 {    
     int mid;    
     Tree[t].left=l,Tree[t].right=r;    
     if(Tree[t].left==Tree[t].right)    
     {    
         Tree[t].num=0;    
         return ;    
     }    
     mid=MID(Tree[t].left,Tree[t].right);    
     Build(L(t),l,mid);    
     Build(R(t),mid+1,r);    
 }    
     
 void Insert(int t,int l,int r,int x)     //向以1为根节点的区间[l,r]插入数字1    
 {    
     int mid;    
     if(Tree[t].left==l&&Tree[t].right==r)    
     {    
         Tree[t].num+=x;    
         return ;    
     }    
     mid=MID(Tree[t].left,Tree[t].right);    
     if(l>mid)    
     {    
         Insert(R(t),l,r,x);    
     }    
     else if(r<=mid)    
     {    
         Insert(L(t),l,r,x);    
     }    
     else    
     {    
         Insert(L(t),l,mid,x);    
         Insert(R(t),mid+1,r,x);    
     }    
     Tree[t].num=Tree[L(t)].num+Tree[R(t)].num;    
 }    
     
 int Query(int t,int l,int r)           //查询以1为根节点，区间[l,r]的和    
 {    
     int mid;    
     if(Tree[t].left==l&&Tree[t].right==r)    
         return Tree[t].num;    
     mid=MID(Tree[t].left,Tree[t].right);    
     if(l>mid)    
     {    
         return Query(R(t),l,r);    
     }    
     else if(r<=mid)    
     {    
         return Query(L(t),l,r);    
     }    
     else    
     {    
         return Query(L(t),l,mid)+Query(R(t),mid+1,r);    
     }    
 }    
   
 int main()  
 {  
     int a,n,i,t,min;  
     long long int k;  
     while(scanf("%d",&n)!=EOF)  
     {  
         memset(Tree,0,sizeof(Tree)); //初始化  
         Build(1,1,n);                //建立线段树  
         for(i=1;i<=n;i++)  
         {  
             scanf("%d",&ans[i].num);  
             ans[i].y=i;  
         }  
         sort(ans+1,ans+1+n,cmp);     //离散化  
         for(i=1;i<=n;i++)            //离散化  
             ans[i].num=i;  
         sort(ans+1,ans+1+n,cmp2);  
         for(i=1,k=0;i<=n;i++)  
         {  
             a=ans[i].num;  
             Insert(1,a,a,1);  
             k=k+(i-Query(1,1,a));    //求出第一个序列的逆序数  
         }  
         min=INF;  
         for(i=1;i<=n;i++)            //O(n)求出所有序列的逆序数，并且取最小的  
         {  
             k=k-(ans[i].num-1)+(n-ans[i].num);  
             if(min>k)  
                min=k;  
          }  
         printf("%d\n",min);  
     }  
     return 0;  
 }  