zercal
C++博客 首页 新随笔 联系 聚合 管理
  10 Posts :: 0 Stories :: 0 Comments :: 0 Trackbacks
拓扑排序求逆序对

 

#include<iostream>
using namespace std;

int a[110000],b[110000],res;//res需要赋初值0 

int merge(int st,int mid,int ed)
{
    int sa,ea,sb,eb,i,j;
    sa=st,ea=mid,sb=mid+1,eb=ed;i=j=0;
    while(sa<=ea&&sb<=eb)
    {
        if(a[sa]<=b[sb])
            b[i++]=a[sa++];
        else{
            b[i++]=a[sb++];
            res+=mid+1-sa;
        }
    }
    while(sa<=ea)
        b[i++]=a[sa++];
    while(sb<=eb)
        b[i++]=b[sb++];
    for(j=0;j<i;j++)
        a[st+j]=b[j];
    return 0;    
}

int mst(int st,int ed)
{
    int mid,i,j,k;
    if(st<ed)
    {
        mid=(st+ed)/2;
        mst(st,mid);
        mst(mid+1,ed);
        merge(st,mid,ed);
    }
    return 0;    
}
posted on 2007-10-06 19:48 zercal 阅读(351) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理