Chinaunix首页 | 论坛 | 博客
  • 博客访问: 2407539
  • 博文数量: 392
  • 博客积分: 7040
  • 博客等级: 少将
  • 技术积分: 4138
  • 用 户 组: 普通用户
  • 注册时间: 2009-06-17 13:03
个人简介

范德萨发而为

文章分类

全部博文(392)

文章存档

2017年(5)

2016年(19)

2015年(34)

2014年(14)

2013年(47)

2012年(40)

2011年(51)

2010年(137)

2009年(45)

分类:

2009-11-30 18:08:08


逆序数
Submit: 1650   Accepted:255
Time Limit: 2000MS  Memory Limit: 20000K
Description
给出一个序列,帮火星人求出该序列的逆序数。


Input
单组测试数据。
第一行为一个整数N,表示序列的长度,(1<= N < 2000000)。
接下来N行,每行一个整数Ai,表示该序列的第i个元素,其中 1<= Ai <= N。


Output
输出仅一行,为该序列的逆序数。


Sample Input

4
3
2
1
4


Sample Output

3



基于merge_sort的逆序数求解


#include <stdio.h>
#include <stdlib.h>

#define WORD sizeof(long)
#define MAX_INT 0x7fffffff

long long reverse;
long array[2000010];
long left[1000010];
long right[1000010];

merge(long *arr, long p, long q, long r)
{
    long i = 0, j = 0, total_len;
    long nleft = q - p + 1;
    long nright = r - q;

#if 0
    long *left = malloc(WORD * (nleft + 1));
    long *right = malloc(WORD * (nright + 1));
#endif
    for (i=0 ; i<nleft ; i++)
    {
        left[i] = arr[p + i];
    }
    left[i] = MAX_INT;
    for (i=0 ; i<nright ; i++)
    {
        right[i] = arr[q + 1 + i];
    }
    right[i] = MAX_INT;

    total_len = nleft + nright + p;
    i = j = 0;
    for (; p<total_len ;p++)
    {
        if (left[i] <= right[j])
        {
            arr[p] = left[i++];
        }
        else
        {
            arr[p] = right[j++];
            reverse += nleft - i; /*count reverse*/
        }
    }

#if 0
    free(left);
    free(right);
#endif
}

merge_sort(long *arr, long p, long r)
{
    if (p < r)
    {
        long q = (p + r) / 2;
        merge_sort(arr, p, q);
        merge_sort(arr, q + 1, r);
        merge(arr, p, q, r);
    }
}

int main(int argc, char *argv[])
{
    long N, i;
    scanf("%ld", &N);
    reverse = 0;
    for (i=0 ; i<N ; i++)
    {
        scanf("%ld", &array[i]);
    }
   
    merge_sort(array, 0, N - 1);

    printf("%lld\n", reverse);
}


阅读(1742) | 评论(0) | 转发(0) |
0

上一篇:LCS pku1458

下一篇:sting迭代器的使用

给主人留下些什么吧!~~