【HDU 1394】Minimum Inversion Number（线段树）

冷不防 2022-04-17 02:08 163阅读 0赞

题目：[点击打开题目链接][Link 1]

题意：输入一个初始序列，然后每次操作都把序列的第一个数放到最后一个位置，构成一个新的序列，问其中某一个序列的最小逆序数是多少。

思路：首先，普及一下逆序与逆序数的概念，简单地说就是如果前面的数比后面的数大，就称为一个逆序。一个排列中逆序的总数称为这个排列的逆序数。

然后这道题有一个好处就是这n个数是由0~n-1组成的，那么，这意味着什么呢？仔细观察后，我们不难发现

假设0~n-1中的一个数x放到了最后一个位置，那么这个序列的逆序数就是n-1-x，这是为什么呢，下面我们接着看

因为在这个序列中，比x小的数有x个（始终记住这n个数是由0~n-1组成的），比x大的数有n-1-x个，那么，将x放到最后一个位置，也就是说，这个序列中的前n-1个数（去掉最后一个数）中有x个比它小的数，有n-1-x个比它大的数，所以这个序列的逆序数就是n-1-x。

我们假设初始序列的逆序数是ans，那么把序列中的x放到最后一个位置之后，逆序数就变成了ans - x +（n-1-x），减x是因为原本x是第一个数，后面有x个比它小的数，现在把它放到了最后一个位置，那么序列中前面有x个对于x来说是有序的，只有那n-1-x个比它大的数才是逆序，所以逆序数要-x。

所以问题就转化成了求初始序列的逆序数，用线段树的方法单点更新，区间求和

主要思想就是把每个数放到自己的叶子结点，然后看它前面有多少个比它大的数，最后累加就是序列的逆序数。

My DaiMa：

#include<iostream>
    #include<stdio.h>
    #include<math.h>
    #include<algorithm>
    using namespace std;
    #define lson l,mid,num<<1
    #define rson mid+1,r,num<<1|1
    const int maxn = 5005;
    int sum[maxn<<2];
    void push_up(int num)
    {
        sum[num] = sum[num<<1] + sum[num<<1|1];
    }
    /*建树*/
    void TreeBuild(int l,int r,int num)
    {
        sum[num] = 0;//初始都是0
        if(l == r) return;
        int mid = (l+r) >> 1;
        TreeBuild(lson);
        TreeBuild(rson);
        push_up(num);
    }
    /*每插入一个数，更新*/
    void update(int x,int l,int r,int num)
    {
        if(l == r)
        {
            sum[num] ++;
            return;
        }
        int mid = (l+r) >> 1;
        if(x > mid) update(x,rson);
        else update(x,lson);
        push_up(num);
    }
    /*查询，判断前面有多少个比它大的数*/
    int query(int x,int y,int l,int r,int num)
    {
        if(x <= l && y >= r) return sum[num];
        int ans = 0;
        int mid = (l+r) >> 1;
        if(x <= mid) ans += query(x,y,lson);
        if(y > mid) ans +=query(x,y,rson);
        return ans;
    }
    int main()
    {
        int n,a[5005];
        while(cin >> n)
        {
            TreeBuild(0,n-1,1);
            int ans = 0;
            for(int i = 0; i < n; i++)
            {
                scanf("%d",&a[i]);
                ans += query(a[i],n-1,0,n-1,1);//先查询
                update(a[i],0,n-1,1);//后更新
            }
            int minn = ans;
            for(int i = 0; i < n; i++)
            {
                ans = ans - a[i] + (n - 1 - a[i]);
                minn = min(minn,ans);
            }
            cout << minn << endl;
        }
    }

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=1394