Minimum Inversion Number HDU - 1394（树状数组求逆序对）

62 阅读 0 评论 41 点赞

我是靠谱客的博主殷勤流沙，最近开发中收集的这篇文章主要介绍Minimum Inversion Number HDU - 1394（树状数组求逆序对），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意：给定一组连续的数，数字为0到n-1。每次将第一个数放在最后，形成一个新的序列。这样一共可以形成n个序列，求这n个序列中逆序对数最少的是多少？

题意解释：假设给定n=5,初始序列为 4 0 2 3 1

那么可以形成 0 2 3 1 4

2 3 1 4 0

3 1 4 0 2

1 4 0 2 3

这5组数，最后要求这5组数中逆序对数最少的数量是多少。

思路：一般的，给定一组数据，求出逆序对应该已经变得和简单了吧（之前写过一篇关于树状数组求逆序对的https://blog.csdn.net/qq_40774175/article/details/86704605）。

这题很友好了，连离散化都不用。

现在考虑如何求移动后的序列逆序对，首先打算n次暴力求解一定会超时的。

因为题目的特殊性，其实我们可以发现一个规律，第一个数能形成的逆序对数量，一定是后面比他小的数的数量，但是，这是一组连续的数，也就是说假如第一个数是3，那么后面一定有1,2 ！所以当3移到后面以后，首先逆序对数量要减少2个，其次当它到了末尾以后，前面比他大的一定可以和它组成逆序对，而前面比他大的数有n-a[i]个，所以要增加n-a[i]个逆序对。

综上所述：每次逆序对的改变量为n-a[i]-(a[i]-1)

为了方便计算，不序列由0-n-1变为1-n即可。

反思：发现这个规律才是解决这题的关键，当然前提是你得会树状数组。

代码：

#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <string>
#include <string.h>
#include <math.h>
#include <sstream>
using namespace std;
typedef long long ll;
const int maxn=1e6+9;
struct BIT
{
    int n;
    ll bit[maxn];
    int lowbit(int  x){return x&-x;}
    void init(int n)
    {
        this->n=n+1;
        memset(bit,0,sizeof(bit));
    }
    void update(int x,int v)
    {
        for(int i=x;i<n;i+=lowbit(i))
        {
            bit[i]+=v;
        }
    }
    ll query(int x)
    {
        ll ans=0;
        for(int i=x;i>0;i-=lowbit(i))
        {
            ans+=bit[i];
        }
        return ans;
    }
}bit;
ll a[maxn];
ll b[maxn];
int main()
{
    #ifndef ONLINE_JUDGE
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        if(n==0) break;
        bit.init(n);
        for(int i=0;i<n;i++)
        {
            scanf("%lld",&a[i]);
            a[i]++;
            //b[i]=a[i];
        }
        //sort(a,a+n);
        // for(int i=0;i<n;i++)
        // {
        //     b[i]=lower_bound(a,a+n,b[i])-(a)+1;
        //     //cout<<b[i]<<endl;
        // }
        ll ans=0;
        for(int i=0;i<n;i++)
        {
            bit.update(a[i],1);
            //cout<<bit.query(b[i])<<endl;
            ans+=(1+i-bit.query(a[i]));
        }
        //cout<<ans<<endl;
        ll M=ans;
        for(int i=0;i<n;i++)
        {
            M+=n-a[i]-(a[i]-1);
            if(M<ans) ans=M;
        }
        cout<<ans<<endl;
    }
    return 0;
}