题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=1394
题目大意: 给出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)
由于给出的序列不是顺序的,所以先要离散化出来
代码:
// 线段树 #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; }
注:原创文章,转载请注明出处