首页 > 代码库 > hdu--1394--加强版的逆序数

hdu--1394--加强版的逆序数

2024-07-11 08:18:13   213人阅读

逆序数 很早前就求过了.

这次 遇到这题 本来以为是很简单的又可以直接求来输出 。

就是要稍微在多加一步先放题目~

　　　　touch me

大概讲下题意：

　　对于一个数组A[n]那么它的元素为A0，A1，A2....An-1

　　我们可以不断地将首位的元素移到最后 形成一个新的序列 就如A2，A3……An-1，A0，A1

　　对于每个这个序列 我们求出它的逆序数~ 这样的序列一共是有n个包括了最初的序列

　　

　　这题解法 大概有3种吧~   线段树   树状数组  归并排序

　　个人最烦 线段树  =-=

　　上午好困 被今天凌晨的巴德 折磨 虐心...

　　我暂时就用 归并做了    晚上有时间 会用树状数组或者线段树去做一次吧 练练~

　　晚些时候 贴上来 ~ （书不在身边 本想写下自己的见解 还是觉得给出最好的比较好...)

 

 

　　这样我们会求出最初那个序列的 逆序数个数为ANS 那另外还有n-1个序列怎么求呢？

　　你这样想 既然我们是要将首位的元素移到末位 那么原先是它的逆序数的个数X现在是不是就不是逆序数了吧？

　　反之 原先不是它的逆序数的个数y现在变成逆序数了！

　　所以 这样进行一次移位后 新的ANS就变成了 ANS - X + Y

　　想通这个 就可以解了

　　

 1 // 归并排序 2  3 #include <iostream> 4 #include <cstring> 5 using namespace std; 6  7 const int size = 5020; 8 int sum; 9 int arr[size];10 int temp[size];11 int cnt[size];12 13 void mergeSort( int x , int y )14 {15     int mid , p , q , i;16     if( y - x >1 )17     {18         mid = x + (y-x) / 2;19         p = x;20         q = mid;21         i = x;22         mergeSort( x , mid );23         mergeSort( mid , y );24         while( p<mid || q<y )25         {26             if( q>=y || ( p<mid && arr[p] <= arr[q]) )27             {28                 temp[i++] = arr[p++];29             }30             else31             {32                 temp[i++] = arr[q++];33                 sum+=(mid-p);34             }35         }36         for( i = x ; i<y ; i++ )37         {38             arr[i] = temp[i];39         }40     }41 }42 43 int main()44 {45     int n , mmin;46     int p , q , num;47     while( ~scanf("%d",&n) )48     {49         sum = 0;50         for( int i = 0 ; i<n ; i++ )51         {52             scanf( "%d",&arr[i] );53             cnt[i] = arr[i];54         }55         mergeSort( 0 , n );56          mmin = sum; 57         for( int i = 0 ; i<n-1 ; i++ )58         {59             p = q = 0;60             num = cnt[0];61             for( int j = 1 ; j < n ; j++ )62             {63                 cnt[j-1]=cnt[j];64                 if( num<cnt[j] )65                 {66                     p++;67                 }68                 else if( num>cnt[j] ) 69                 {70                     q++;71                 }72             }73             sum+=(p-q);74             if(sum<mmin) 75             {76                 mmin = sum;77             }78             cnt[n-1]=num;79         }80         printf( "%d\n",mmin );81     }82     return 0;83 }
View Code

 

today:

　　你的喜贴是我的请贴
　　你邀我举杯
　　我只能回敬我的崩溃
　　在场的都知道
　　你我曾那么好
　　如今整颗心都碎了
　　你还要我微笑

 

 

 

 

 

 

　　

 

 

 

 

 

 

 

 

 

 

 

 

 

 

　　


联系
我们