归并排序 题解即模版 XMU1328 hdu3743

归并排序 例题即模版 XMU1328 hdu3743

#include <stdio.h>  #include <stdlib.h>  #define MAXN 1000100  int input[MAXN] = {0};  int tmp[MAXN];   void merge(int left, int middle, int right)  {       int i, j, k;       i = left, j= middle+1, k = 1;       while(i<= middle && j <= right)       {                 if(input[j] < input[i])                 {                      tmp[k++] = input[j++];                 }                 else          {                      tmp[k++] = input[i++];          }       }       while(i <= middle)        tmp[k++] = input[i++];       while(j <= right)       tmp[k++] = input[j++];            for(i = left, k = 1; i<= right; i++, k++)              input[i] = tmp[k];  }  void merge_sort(int left, int right)  {       if(left < right)       {               int middle = (left + right)/2;               merge_sort(left, middle);               merge_sort(middle+1, right);               merge(left, middle, right);       }  }  int main(){      int n,i;  while( scanf("%d",&n)&&n){    for(i=0;i<n;++i)          scanf("%d",&input[i]);      merge_sort(0,n-1);      for(i=0;i<n-1;++i)  printf("%d ",input[i]);printf("%d\n",input[i]);}    return 0;  }   

上面是模版

只要看下代码 就能理解是如何实现的了

 

下面是一个应用 XMU1328

1328.不高兴的boboTime Limit: 2000 MS         Memory Limit: 65536 K
Total Submissions: 589 (85 users)         Accepted: 55 (42 users)

Description

Bobo手下有n个小弟，身高分别是a1，a2……an，bobo看他们高矮不一，于是很不高兴，定义有两个小弟不按高矮站时，bobo的不高兴值加1（即(i,j)，i<j,ai>aj），问bobo的总不高兴值为多少。

Input

一个整数n，表示bobo有n个小弟。

以下有n个整数ai，代表小弟的身高。

N<=10^6,ai<2^32

Output

一个整数为bobo的不高兴值。

Sample Input

5

5 4 3 2 1

Sample Output

10

 

Problem DescriptionInputOutputSample InputSample OutputSource

 

#include<stdio.h>#include<malloc.h>int ans;/////////////// 精度__int64 a[1000000+50];void merge(int left,int mid,int right){    int i,j,cnt=0;    int *p;    p=(int *)malloc((right-left+1)*sizeof(int));    i=left;    j=mid+1;    while(i<=mid&&j<=right)//这时候i 和 j 指向的部分都排序完毕了 现在合并    {        if(a[i]<=a[j])        {            p[cnt++]=a[i];            i++;        }        else         {            p[cnt++]=a[j];            j++;            ans+=mid-i+1;//第i个比j大 由于i已经从小到大排过序了 那么i+1到mid的也会比j大        }    }    while(i<=mid)    {        p[cnt++]=a[i++];    }    while(j<=right)     {        p[cnt++]=a[j++];    }    cnt=0;    for(i=left;i<=right;i++)        a[i]=p[cnt++];    free(p);    }void merge_sort(int left,int right){    if(left<right) //长度大于1  这是个判断不是循环    {        int mid;        mid=(left+right)/2;        merge_sort(left,mid);        merge_sort(mid+1,right);        merge(left,mid,right);    }}int main(){    int n,i;    while(scanf("%d",&n)!=EOF)    {        ans=0;        for(i=0;i<n;i++)            scanf("%d",&a[i]);        merge_sort(0,n-1);        printf("%I64d\n",ans);//////////    }    return 0;} 

查看更多 下一篇