hihocoder-1524-逆序对

hihocoder-1524-逆序对

#1524 : 逆序对

时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述

给定一个1-N的排列A1, A2, ... AN，如果Ai和Aj满足i < j且Ai > Aj，我们就称(Ai, Aj)是一个逆序对。

求A1, A2 ... AN中所有逆序对的数目。

输入

第一行包含一个整数N。

第二行包含N个两两不同整数A1, A2, ... AN。(1 <= Ai <= N)

对于60%的数据 1 <= N <= 1000

对于100%的数据 1 <= N <= 100000

输出

一个整数代表答案

样例输入

5
3 2 4 5 1

样例输出

经典的用merge sort 来解决逆序对的问题。

#include <cstdio> 
const int MAXN = 1e5 + 10; 
const int MOD = 1000000007; 

int  num[MAXN], tmp[MAXN]; 
long long cnt; 

void Merge_Sort(int l, int r){
    int mid = l + (r - l)/2; 
    int p = l, p1 = l, p2 = mid + 1; 
    while(p1<=mid && p2<=r){
        if(num[p1] > num[p2]){
            tmp[p++] = num[p2++]; 
            cnt += (mid - p1 + 1); 
        }else{
            tmp[p++] = num[p1++]; 
        }
    }
    while(p1<=mid){
        tmp[p++] = num[p1++]; 
    }
    while(p2<=r){
        tmp[p++] = num[p2++]; 
    }
    for(int i=l; i<=r; ++i){
        num[i] = tmp[i]; 
    } 
}

void Merge(int l, int r){
    if(l >= r ){ return; } 
    int mid = l + (r - l)/2; 
    Merge(l, mid); 
    Merge(mid+1, r); 
    Merge_Sort(l, r); 
}

int main(){
    int n; 
    while(scanf("%d", &n) != EOF){
        for(int i=0; i<n; ++i){
            scanf("%d", &num[i]); 
        }
        cnt = 0; 
        Merge(0, n-1); 
        printf("%lld
", cnt );
    }
    return 0; 
}

方法二，参考了网友的answer，因为 num 的range 是 [1, n] ，所以，可以采用树状数组。只需要对 num 一个一个插入到 dp[] 数组中，快速计算 sum即可。

#include <cstdio> 
#include <cstring>
const int MAXN = 1e5 + 10; 
const int MOD = 1000000007; 

long long cnt; 
int n, num[MAXN], dp[MAXN]; 

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

long long GetSum(int pt){
    long long ans = 0; 
    int i = pt; 
    while(i <= n){
        ans += dp[i]; 
        i +=  lowbit(i); 
    } 
    return ans; 
}

void AddNum(int pt, int v){
    int i = pt; 
    while(i > 0){
        dp[i] += v; 
        i -= lowbit(i); 
    }
}

int main(){
    freopen("in.txt", "r", stdin); 

    while(scanf("%d", &n) != EOF){
        for(int i=0; i<n; ++i){
            scanf("%d", &num[i]); 
        }
        memset(dp, 0, sizeof(dp)); 
        cnt = 0; 
        for(int i=0; i<n; ++i){
            cnt += GetSum(num[i]); 
            AddNum(num[i], 1); 
        }
        printf("%lld
", cnt );
    }
    return 0; 
}