HDOJ1394 Minimum Inversion Number【线段树】-阿里云开发者社区

开发者社区> 云计算> 正文
登录阅读全文

HDOJ1394 Minimum Inversion Number【线段树】

简介:
复制代码
//往线段树中添加数据,每个结点记录的是
//当前结点范围已经插入的数字个数
//如果p点在左子树上,就累加右子树根节点上的记录
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define maxn 5001
int sum[maxn<<2],num[maxn+1];
int Min,s;
void build()
{
    memset(sum,0,sizeof(sum));
}
void insert(int p,int l,int r,int rt)
{
    int m;
    if(l<=p&&p<=r)
        sum[rt]++;
    if(l==r)
        return;
    m=((l+r)>>1);
    if(p<=m)
    {
        insert(p,lson);
        s+=sum[rt<<1|1];
    }        
    if(p>m)
        insert(p,rson);
}
int main()
{
    int n,i;
    while (scanf("%d",&n)!=EOF)
    {
        //初始化
        s=0;
        build();
        //统计,得到s值
        for (i=0;i<n;i++)
        {
            scanf("%d",&num[i]);
            insert(num[i]+1,1,n,1);
        }
        //求出Min
        Min=s;
        for (i=0;i<n;i++)
        {
            s=s-num[i]+n-1-num[i];
            Min=Min<s?Min:s;
        }
        printf("%d\n",Min);
    }
    return 0;
}
复制代码

 


本文转自ZH奶酪博客园博客,原文链接:http://www.cnblogs.com/CheeseZH/archive/2012/04/28/2475573.html,如需转载请自行联系原作者

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享: