注册 登录  
 加关注

网易博客网站关停、迁移的公告:

将从2018年11月30日00:00起正式停止网易博客运营
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

zxj015

 
 
 

日志

 
 

poj 2299 Ultra-QuickSort 归并排序求解逆序对  

2011-04-07 11:33:04|  分类: 数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://poj.org/problem?id=2299
给定一个整数数列,相邻之间的数可以互换,求最少要多少次互换后得到一个升序数列。
本题说白了就是求解逆序对问题(关于逆序对请参考:http://baike.baidu.com/view/689576.htm),接下来便是用归并排序来解逆序对了。
#include <stdio.h>
#include <stdlib.h>
 
#define MAX 500001
 
int n, a[MAX], t[MAX];
__int64 sum;
 
void Merge(int l, int m, int r)
{
    int p = 0;
    int i = l, j = m + 1;
    while(i <= m && j <= r)
    {
        if (a[i] > a[j])
        {
            t[p++] = a[j++];
            sum += m - i + 1; //why?因为如果a[i] > a[j]的话,那么a[i]到a[m]之间的所有数都可以和a[j]构成逆序对。这句 是本题的核心。
        }
        else
        {
            t[p++] = a[i++];
        }
    }
    while(i <= m) t[p++] = a[i++];
    while(j <= r) t[p++] = a[j++];
    for (i = 0; i < p; i++)
    {
        a[l + i] = t[i];
    }
}
void MergeSort(int l, int r)
{
    int m;
    if (l < r)
    {
        m = (l + r) / 2;
        MergeSort(l, m);
        MergeSort(m + 1, r);
        Merge(l, m, r);
    }
}
 
int main()
{
    int i;
    while(1)
    {
        scanf("%d", &n);
        if (n == 0) break;
        sum=0;
        for(i = 0; i < n; i++)
        {
            scanf("%d", &a[i]);
        }
        MergeSort(0, n - 1);
        printf("%I64d\n", sum);
    }
    return 0;
}

  评论这张
 
阅读(152)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018