hdu 1394 Minimum Inversion Number-阿里云开发者社区

开发者社区> 云计算> 正文
登录阅读全文

hdu 1394 Minimum Inversion Number

简介: 点击打开hdu 1394 思路: 树状数组 分析: 1 题目要求的是n个数的n个序列中找到的最小逆序数对 2 首先我们都知道所谓的逆序数对就是给一个序列,如果前面的数比当前的数大,那么这两个数就是逆序数对。

点击打开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;
}




版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享: