soj1798归并排序.cpp

一些ACM题目的解答,主要是soj和poj的

#include<stdio.h>
#include<string.h>

int num[2000];
int temp[2000];
long step;

void merge(int left,int right)
{
    int center=(left+right)/2;
    int i=left,j=center+1,help=left;
    while(i<=center&&j<=right)
    {
        if(num[i]>num[j])
        {
            step+=j-help;
            temp[help++]=num[j++];
        }
        else
        {
            temp[help++]=num[i++];
        }
    }
    while(i<=center)
    {
        temp[help++]=num[i++];
    }
    while(j<=right)
    {
        temp[help++]=num[j++];
    }
    for(i=left;i<=right;i++)
        num[i]=temp[i];
}
        
void mergesort(int left,int right)
{
    if(right<=left)
        return ;
    int center=(left+right)/2;
    mergesort(left,center);
    mergesort(center+1,right);
    merge(left,right);
}

int main(void)
{
    int t;
    scanf("%d",&t);
    int i;
    for(i=1;i<=t;i++)
    {
        step=0;
        memset(num,0,sizeof(num));
        memset(temp,0,sizeof(temp));
        int n;
        int j;
        scanf("%d",&n);
        for(j=0;j<n;j++)
        {
            scanf("%d\n",num+j);
        }
        mergesort(0,n-1);
        printf("Scenario #%d:\n%d\n\n",i,step);
    }
    return 0;
}