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

Ultra-QuickSort

Description

In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. For the input sequence

9 1 0 5 4 ,

0 1 4 5 9 .

Input

The input contains several test cases. Every test case begins with a line that contains a single integer n < 500,000 -- the length of the input sequence. Each of the the following n lines contains a single integer 0 ≤ a[i] ≤ 999,999,999, the i-th input sequence element. Input is terminated by a sequence of length n = 0. This sequence must not be processed.

Output

For every input sequence, your program prints a single line containing an integer number op, the minimum number of swap operations necessary to sort the given input sequence.

Sample Input

59105431230

Sample Output

60

Source

大致题意：

给出长度为n的序列，每次只能交换相邻的两个元素，问至少要交换几次才使得该序列为递增序列。

解题思路:

跟POJ1804要求一样，区别是这个数组的范围最大为50W

所以之前使用的冒泡方法O(n^2)，复杂度铁定超肯定是会超时的。

直接用快排又不符合题目的要求（相邻元素交换），快排是建立在二分的基础上的，

操作次数肯定比在所要求的规则下的交换次数要更少 那么该怎么处理？

其实这题题目已经给出提示了：

Ultra-QuickSort 特殊的快排，能和快排Quicksort相媲美的就是归并排序Mergesort了，

O(nlogn) 但是用归并排序并不是为了求交换次数，而是为了求序列的 逆序数

一个乱序序列的 逆序数 = 在只允许相邻两个元素交换的条件下, 得到有序序列的交换次数

代码：

#include
   
    #include
    
     #include
     
      #define ll long long#define MAX  2147483647#define fi first#define se second#define fo(i,a,b) for(int i=(a);i<=(b);++i)#define fodown(i,a,b) for(int i=(a);i>=(b);i--)using namespace std;int n,a[500005],b[5000005];ll ans;int read(){   int x=0,tmp=1;   char ch=getchar();   while(ch<'0' || ch>'9' ) { if(ch=='-') tmp=-1;ch=getchar();}   while(ch>='0'&& ch<='9') { x = x * 10+ ch-'0';ch=getchar();}   return x*tmp;}void merge(int l,int m,int r){    int i=l,j=m+1,tot=l-1;    while(i<=m&&j<=r)    {        if(a[i]<=a[j]) b[++tot]=a[i],i++;        else        {            b[++tot]=a[j];            ans+=m-i+1;/*我们能保证(l,m)这个区间是升序的，这是显然的，因为先排序这个区间，再排序整个区间，如果a[j]
      
       >1;    qsort(l,mid);//分块    qsort(mid+1,r);    merge(l,mid,r);}int main(){  // freopen(" .in","r",stdin);  // freopen(" .out","w",stdout);   while(scanf("%d",&n)!=EOF&&n)   {      fo(i,1,n) a[i]=read();      ans=0;      qsort(1,n);       cout<
       
        <
       
      
     
    
   

其实还有另一种高大上的求法：树状数组

具体理解：

# define Name ""# include 
   
    # include 
    
     # include 
     
      # include 
      
       # define LL long longusing namespace std ;const int N = 5e5 + 10 ;int a [N] , b [N] , c [N] , n ;int lowbit ( int x ) {    return ( - x ) & x ;}void modify ( int pos , int val ) {    for ( int i = pos ; i <= n ; i += lowbit ( i ) )         c [i] += val ;}int query ( int pos ) {    int ret = 0 ;    for ( int i = pos ; i >= 1 ; i -= lowbit ( i ) )         ret += c [i] ;    return ret ;}int main () {    while ( scanf ( "%d" , & n ) != EOF && n ) {        memset ( c , 0 , sizeof c ) ;        for ( int i = 1 ; i <= n ; ++ i ) scanf ( "%d" , & a [i] ) , b [i] = a [i] ;        sort ( a + 1 , a + 1 + n ) ;        for ( int i = 1 ; i <= n ; ++ i ) b [i] = lower_bound ( a + 1 , a + 1 + n , b [i] ) - a ;        LL ans = 0 ;        for ( int i = 1 ; i <= n ; ++ i ) {            modify ( b [i] , 1 ) ;             ans += i - query ( b [i] ) ;        }        printf ( "%lld\n" , ans ) ;     }    return 0 ;}
      
     
    
   

转载地址：https://joycez.blog.csdn.net/article/details/83096932 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！