这题是一道线段树的应用..不说简单..因为搞了几天..一度觉得自己很笨,怎么这个代码都看不懂...哭晕在厕所..
找了好多人的代码...最后静下心看了 " 紫忆 " 的代码 .. 终于看懂了..谢天谢地..
很感谢所有能够分享自己成果的大神们!!不然渣渣没办法活了..当然还是杭电这个平台好啊..
注释都写到代码里面了..看代码即可..
1 //线段树方法是将对应值对应到线段树的最底部的位置,然后通过每次O(logn)查询加快速度. 2 //最后采用一个公式:将某一个数向后移动,增加的逆序数为 n-a[i]-1 ,减少 a[i],最后找到最小值; 3 //个人想法:这个方法如果数组的数大于n就用不了了,因为没有下标... 4 //看了 紫忆 的代码写的, 5 #include <iostream> 6 #include <string.h> 7 using namespace std; 8 #define maxn 5005 9 struct node{ 10 int left , right , sum ; 11 }segment[maxn<<2]; 12 int num[maxn]; 13 void buildTree(int rt,int left,int right)//建树; 14 { 15 segment[rt].left = left; 16 segment[rt].right = right ; 17 segment[rt].sum = 0; 18 if(left == right) 19 { 20 return ; 21 } 22 int mid = (left + right) >> 1; 23 buildTree(rt<<1,left,mid); 24 buildTree(rt<<1|1,mid+1,right); 25 } 26 int query(int rt,int value,int n)//查询[value+1,n-1]中数的数量; 27 { 28 if(value <= segment[rt].left && segment[rt].right <= n) 29 return segment[rt].sum; 30 else 31 { 32 int mid = (segment[rt].left + segment[rt].right)>>1; 33 int sum1 = 0 , sum2 = 0; 34 if(value <= mid ) 35 sum1 = query(rt<<1,value,n); 36 if(n > mid) 37 sum2 = query(rt<<1|1,value,n); 38 return sum1+sum2; 39 } 40 41 } 42 void update(int rt,int value) 43 { 44 if(segment[rt].right == value && segment[rt].left == value)//将value所对应的位置元素置为1; 45 { 46 segment[rt].sum = 1; 47 return ; 48 } 49 int mid = (segment[rt].left + segment[rt].right)>>1; 50 if(value <= mid) 51 update(rt<<1,value); 52 else 53 update(rt<<1|1,value); 54 segment[rt].sum = segment[rt<<1].sum + segment[rt<<1|1].sum;//更新 55 } 56 int main() 57 { 58 int n; 59 while(scanf("%d",&n)>0) 60 { 61 buildTree(1,0,n-1); 62 int ans = 0; 63 for(int i = 0 ; i < n ; i ++) 64 { 65 scanf("%d",num+i); 66 ans += query(1,num[i]+1,n-1); 67 update(1,num[i]); 68 } 69 int min_sum = ans ; 70 for(int i = 0; i <n ;i ++) 71 { 72 ans += n - 2*num[i] - 1 ; // 增加的逆序数和减少的逆序数 n-num[i]-1 和 num[i]; 73 if(min_sum > ans) 74 min_sum = ans ; 75 } 76 printf("%d ",min_sum); 77 } 78 return 0; 79 }