首页 > 代码库 > HDU 1394 Minimum Inversion Number (线段树 单点更新 求逆序数)

HDU 1394 Minimum Inversion Number (线段树 单点更新 求逆序数)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1394

题意:给你一个n个数的序列,其中组成的数只有0-n,我们可以进行这么一种操作:把第一个数移到最后一个,次数不限。问,在原始数列和最新生成的数列中逆序数最小可以是多少?


刚开始以为需要枚举求逆序数,但最后知道了这个题是有规律的:一个由0-n组成的n个数的数列,当第一个数移到最后一位的时候,整个数列的逆序数会减少x[i](移动前,后面比他小的),会增加n-x[i]-1(移动后,前面比他大的)。

那么这个题就成了单纯求原始数列的逆序数。

之前求逆序数用过归并,也用过线段树,可惜没总结,当时的题目还需要离散化。现在先总结这个简单的,等继续回顾暑假内容的时候会遇到的。

线段树求逆序数

因为线段树善于解决区间问题,那么我们可以用它快速区间求和,我们把每个数纳入线段树,当新录入一个数之前,统计已经录入的几个数比他大,以此类推,最后的统计和就是逆序数。


代码:

#include <iostream>
#include <cstdio>
#include <algorithm>
#define LS rt << 1
#define RS rt << 1 | 1
#define LSON l,m,rt << 1
#define RSON m + 1,r,rt << 1 | 1
#define MID (l + r) >> 1
#define MAX 5000

using namespace std;

int num[MAX << 2];
int x[MAX + 10];

inline void pushup(int rt)
{
    num[rt] = num[LS] + num[RS];
}

void build(int l,int r,int rt)
{
    num[rt] = 0;

    if(l == r)
        return ;

    int m = MID;
    build(LSON);
    build(RSON);
}

void update(int p,int l,int r,int rt)
{
    if(l == r)
    {
        num[rt]++;
        return ;
    }

    int m = MID;

    if(p <= m)
        update(p,LSON);
    else
        update(p,RSON);

    pushup(rt);
}

int query(int ql,int qr,int l,int r,int rt)
{
    if(l >= ql && r <= qr)
    {
        return num[rt];
    }

    int m = MID;
    int ret = 0;

    if(ql <= m)
        ret += query(ql,qr,LSON);
    if(qr > m)
        ret += query(ql,qr,RSON);

    return ret;
}

int main()
{
    int n;

    while(~scanf("%d",&n))
    {
        int sum = 0;

        build(0,n - 1,1);

        for(int i = 0;i < n;i++)
        {
            scanf("%d",&x[i]);
            sum += query(x[i],n - 1,0,n - 1,1);
            update(x[i],0,n - 1,1);
        }

        int ans = sum;

        for(int i = 0;i < n;i++)
        {
            //0-n的数,把第一个数移到最后一位后
            //整个数列的逆序数会减少x[i](移动前,后面比他小的)
            //会增加n-x[i]-1(移动后,前面比他大的)
            sum += n - x[i] - x[i] - 1;
            ans = min(ans,sum);
        }

        printf("%d\n",ans);
    }
    return 0;
}


HDU 1394 Minimum Inversion Number (线段树 单点更新 求逆序数)