归并排序法---题目

时间：2016-02-29 23:11:50 阅读：296 评论：0 收藏：0 [点我收藏+]

题目内容：

在一個N個數字的序列S裡，當S[i] > S[j] 且 i < j的時候，我們說(i ,j)是一個逆序數對。

Hint : 利用歸併排序法計算一個序列裡有多少逆序數對。

Hint : 思考一下在merge的過程，怎麼找到答案!

Hint : 直接使用兩層迴圈來找答案的話會超過系統時間限制。

输入格式:

只有一筆測資，第一行為一個數字N，代表接下來有N行，每行有一個數字。這N個數字都會相異。

數字範圍：

0 < N < 20000

输出格式：

輸出一行數字，該序列的逆序數對個數。

输入样例：

输出样例：

时间限制：100ms内存限制：128000kb

#include <stdio.h>
#include <stdlib.h>
int sum = 0;
void merge(int arr[],int first,int mid,int last){
    int first1 = first;
    int last1 = mid;
    int first2 = mid+1;
    int last2 = last;
    int i,index=0;
 
     
    int *temp;
    temp = (int *)malloc((last-first+1)*sizeof(int));
    if(temp == NULL){
        return;
    }
     
    while((first1<=last1)&&(first2<=last2)){
        if(arr[first1]<arr[first2]){
            temp[index++] = arr[first1++];
        }else{
             
            temp[index++] = arr[first2++];    
            sum += (first2-frist) - index;  //尤其注意这一条语句
        }
    }
     
    while(first1<=last1){
        temp[index++] = arr[first1++];
    }
     
    while(first2<=last2){
        temp[index++] = arr[first2++];
    }
     
    for(i=0;i<index;i++){
        arr[first+i] = temp[i];
    }
 
    free(temp);
     
 
}
 
void mergesort(int arr[],int first,int last){
    int mid = 0;
    if(first<last){
        mid = (first+last)/2;
        mergesort(arr,first,mid);
        mergesort(arr,mid+1,last);
        merge(arr,first,mid,last);      
    }
     
}
 
int main(void){
    int n;
    int j;
    int arr[200];
    scanf("%d\n",&n);
         
    for(j = 0; j<n; j++){
        scanf("%d",&arr[j]);
    }
 
    mergesort(arr,0,n-1);
    printf("%d\n",sum);
    return 0;
}

归并排序法---题目

原文：http://www.cnblogs.com/fuchen1994/p/5229029.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)