hdu 1394 归并排序

http://acm.hdu.edu.cn/showproblem.php?pid=1394

#include<stdio.h>

#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<algorithm>
using namespace std;


const int sizen=100000;
int a[sizen],b[sizen],c[sizen];
int t;
int num;


void Merge(int x,int Mid,int y)
{
    int i,j;
    i=x;
    j=Mid+1;
    t=i;
    while(i<=Mid&&j<=y)
    {
        if(a[i]<a[j])
            b[t++]=a[i++];
        else
            b[t++]=a[j++],num+=(Mid-i+1);
    }
    while(i<=Mid)
        b[t++]=a[i++];
    while(j<=y)
        b[t++]=a[j++];
    for(i=x;i<=y;i++)
        a[i]=b[i];
}


void merge_sort(int x,int y)
{
    if(x==y)
        return;
    int Mid=(x+y)>>1;
    merge_sort(x,Mid);
    merge_sort(Mid+1,y);
    Merge(x,Mid,y);
}


int main()
{
    int n;
    int i;
    while(scanf("%d",&n)!=EOF)
    {
        num=0;
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            c[i]=a[i];
        }


        merge_sort(1,n);
        int ans=num;
        for(i=1;i<n;i++)
        {
            num-=c[i];
            num+=(n-1-c[i]);
            if(ans>num)
                ans=num;
        }
        printf("%dn",ans);
    }
    return 0;
}

最后

以上就是聪慧金鱼最近收集整理的关于hdu 1394 归并排序的全部内容，更多相关hdu内容请搜索靠谱客的其他文章。