hdu 1394 Minimum Inversion Number

点击打开hdu 1394

思路: 树状数组

分析:

1 题目要求的是n个数的n个序列中找到的最小逆序数对

2 首先我们都知道所谓的逆序数对就是给一个序列，如果前面的数比当前的数大，那么这两个数就是逆序数对。比如4 1 3 2中逆序数有 4 1, 4 3, 4 2, 3 2

3 那么我们可以很快的利用树状数组求出起始数组的逆序数对，那么我们接下来考虑把第一个数换到最后一个位置的情况

假设现在起始的序列的逆序数对有sum，那么第一个数num[1]换到最后一个位置的后果就是使得所有比num[i]小的数度不能和num[i]构成逆序数了，那么直接减少的个数就是n-1-num[i]，但是那么比num[i]大的数可以和num[i]构成逆序数，因此增加了n-num[i]个。因此换完之后的序列的逆序数对为sum-(n-1-num[i])+n-num[i];

4 因此我们只要去做n次的比较，求出的最小值即为ans

代码:

/************************************************
 * By: chenguolin                               * 
 * Date: 2013-08-21                             *
 * Address: http://blog.csdn.net/chenguolinblog *
 ***********************************************/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long int64;
const int MAXN = 5010;

int n , ans;
int num[MAXN];
int treeNum[MAXN];

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

int64 getSum(int x){
    int sum = 0;
    while(x){
        sum += treeNum[x];
        x -= lowbit(x);
    }
    return sum;
}

void add(int x , int val){
    while(x < MAXN){
        treeNum[x] += val;
        x += lowbit(x);
    }
}

int64 solve(){
    int sum = ans;
    for(int i = 1 ; i <= n ; i++){
        sum = sum-(num[i]-1)+(n-num[i]);
        ans = min(ans , sum);
    }
    return ans;
}

int main(){
    while(scanf("%d" , &n) != EOF){
        memset(treeNum , 0 , sizeof(treeNum));
        ans = 0;
        for(int i = 1 ; i <= n ; i++){
            scanf("%d" , &num[i]);
            num[i]++;
            ans += i-1-getSum(num[i]-1);
            add(num[i] , 1);
        }
        printf("%lld\n" , solve());
    }
    return 0;
}