国内最全IT社区平台 联系我们 | 收藏本站
华晨云阿里云优惠2
您当前位置:首页 > php开源 > php教程 > hdu1394Minimum Inversion Number树状数组求逆序对水题

hdu1394Minimum Inversion Number树状数组求逆序对水题

来源:程序员人生   发布时间:2015-03-09 08:49:43 阅读次数:3278次
//ans[i]=ans[i⑴]+(n+1)⑵*num[i]
//num[i]为输入时的数据
//ans[i]为m=i时的逆序数
//用树状数组求ans[0]的逆序对
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=5010;
int num[maxn];
int tree[maxn];
int lowbit(int i)
{
    return i&(-i);
}
int getsum(int i)
{
    int sum=0;
    while(i>0)
    {
        sum+=tree[i];
        i-=lowbit(i);
    }
    return sum;
}
void update(int i,int dx)
{
    while(i<maxn)
    {
        tree[i]+=dx;
        i+=lowbit(i);
    }
}
int main()
{
    int n;int i;
    while(scanf("%d",&n)!=EOF)
    {
        memset(tree,0,sizeof(tree));
        int ans[maxn];
        memset(ans,0,sizeof(ans));
        for(i=1;i<=n;i++)
        {
            scanf("%d",&num[i]);
            num[i]++;
            ans[0]+=(i⑴)-getsum(num[i]);
            update(num[i],1);
        }
        int sum=ans[0];
        for(i=1;i<=n;i++)
        {
            ans[i]=ans[i⑴]+(n+1)⑵*num[i];
            sum=min(ans[i],sum);
        }
        printf("%d ",sum);
    }
}



































































































生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生