HDU1394用树状数组求逆序数

72 阅读 0 评论 48 点赞

我是靠谱客的博主自觉乐曲，最近开发中收集的这篇文章主要介绍HDU1394用树状数组求逆序数，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意：一个由0..n-1组成的序列，每次可以把队首的元素移到队尾，求形成的n个序列最小逆序对数目
算法：
由树状数组求逆序对。加入元素i即把以元素i为下标的a[i]值+1，从队尾到队首入队，
每次入队时逆序对数 += getsum(i - 1),即下标比它大的但是值比它小的元素个数。
因为树状数组不能处理下标为0的元素，每个元素进入时+1，相应的其他程序也要相应调整。
求出原始的序列的逆序对个数后每次把最前面的元素移到队尾，逆序对数即为

原逆序对数+比i大的元素个数-比i小的元素个数，因为是0..n,容易直接算出，每次更新min即可。

#include <stdio.h>
#define MAXN 10000

int c[MAXN],a[MAXN],n;

int min(int a,int b)
{
    if (a < b) return a;
    else return b;
}

int lowbit(int i)
{
    return i & -i;
}


void update(int i,int x)
{
    while (i <= n)
    {
        c[i] += x;
        i += lowbit(i);
    }
}

int getsum(int x)
{
    int sum = 0;
    while (x > 0)
    {
        sum += c[x];
        x -= lowbit(x);
    }
    return sum;
}

int main()
{
    while (scanf("%d", &n) == 1)
    {
        for (int i = 1; i <= n; i++)
            c[i] = 0;
        int sum = 0;
        for (int i = 1; i <= n; i ++)
        {
            scanf ("%d", &a[i]);
        }
        for (int i = n; i >= 1; i --)
        {
            update (a[i] + 1, 1);
            sum += getsum (a[i]);
        }
        int ans = sum;
        for (int i = 1; i <= n; i++)
        {
            sum = sum - a[i] + (n - a[i] - 1);
            ans = min(ans, sum);
        }
        printf("%dn", ans);
    }
    return 0;
}