首页 > 代码库 > poj 2299 Ultra-QuickSort(归并排序)

poj 2299 Ultra-QuickSort(归并排序)

2024-11-22 00:37:02   204人阅读

题意 ：交换相邻的两个数来排序 最少交换几次

 

思路：

题意可以转化成求 数列中存在几个逆序数

可以看作冒泡排序 但是复杂度过高 用归并排序来完成

（注意 n<=5000000 所以ans 要用 长整型 ）

 

#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;int a[5000000+100];int t[5000000+100];__int64 ans;int l,r;void merge(int x,int y){    if(y-x>1)    {        int m=x+(y-x)/2;        int p=x,q=m,i=x;        merge(x,m);        merge(m,y);        while(p<m||q<y)        {            if(q>=y||(p<m&&a[p]<=a[q])) t[i++]=a[p++];            else                {                    if(p<m)                    {                        //printf("%d %d...\n",a[p],a[q]);                        ans+=(m-p);                    }                    t[i++]=a[q++];                }        }        for(i=x;i<y;i++) a[i]=t[i];       // printf("%d %d %d\n",x,m,y);  for(i=0;i<r;i++) printf("%d ",a[i]);  printf("\n\n\n");    }}int main(){    int n;    int i,j,k;    while(scanf("%d",&n),n)    {        ans=0;        for(i=0;i<n;i++)        {            scanf("%d",&a[i]);        }        //l=0;r=n;        merge(0,n);        printf("%I64d\n",ans);    }    return 0;}

 

poj 2299 Ultra-QuickSort(归并排序)


联系
我们