poj 2299 逆序数

http://poj.org/problem?id=2299

坑：答案是long long 输出……！！！！！

题意是：求一个数组进行冒泡排序交换的次数

题解：求逆序数

题解Ⅰ：

归并排序求逆序数

归并排序求逆序数之前写过

1.归并排序是把两个有序的数组合并成为一个有序的数组，利用分治的思想就可以进行排序

　　逆序数可以利用这个思想求

　　求出第一个数组的逆序数，和第二个数组的逆序数，再将两个数组整体的逆序数求出来

　　f(x,y) = f(x,mid) + f(mid,y) + 之后数组的逆序数

#include <iostream>

#include <cstring>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <algorithm>

#include <cstdlib>

#include <vector>

#include <map>

#include <queue>

#include <stack>

const int MAXN =   + ;

const int INF = 0x7fffffff;

const int MOD = ;

const double ESP = 10e-;

const double Pi = acos(-1.0);

typedef long long LL;

using namespace std;

LL a[MAXN];

LL b[MAXN];

LL h(int s,int e){

    if(e-s <= ){

        return ;

    }

    int mid = s + (e-s)/;

    LL x = h(s,mid);

    LL y = h(mid,e);

    int p1 = s;

    int p2 = mid;

    int p3 = s;

    LL cnt = ;

    while(p1 < mid || p2 < e){

        if(p2 >= e || (p1 < mid && a[p1] < a[p2])){

            b[p3++] = a[p1++];

        }

        else{

            b[p3++] = a[p2++];

            cnt += (mid-p1); /*第二个数组当前元素比第一个数组当前元素小，所以第一个数组从当前元素到最后的元素都比第二个数组的大（数组一，二都已经有序了），所以第一个数组结尾下标，减去第一个数组的当前元素就是两个数组的逆序数*/

        }

    }

    for(int i = s;i < e;i++){

        a[i] = b[i];

    }

    return x+y+cnt;

}

int main(){

    //freopen("input.txt","r",stdin);

    int n;

    while(~scanf("%d",&n) && n){

        for(int i = ;i < n;i++){

            scanf("%d",&a[i]);

        }

        LL ans = h(,n);

        printf("%lld\n",ans);

    }

    return ;

}

题解Ⅱ：

http://www.cnblogs.com/shenshuyang/archive/2012/07/14/2591859.html

这个童鞋写得已经很棒了
1.数组元素太大，而n 的个数又很少，所以需要离散化

离散化：

用struct Node{

　　int v;

　　int order;

};

将元素读入，并且将元素的次序读入

将元素排序之后，下标的标号一定程度上是代表元素的大小

所以用下标的标号就可以表示元素

这样范围就减少了

树状数组是求前 i 个元素的和

先 add(a[i],1)

再 i - sum(a[i])

前面已经有 i 个元素了，sum(a[i]) 表示 1 - a[i] 的和，而 i - sum(a[i]) 表示有多少个数字比 a[i] 大但是次序却在 i 位置的前面就是 a[i] 元素的逆序数

#include <iostream>

#include <cstring>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <algorithm>

#include <cstdlib>

#include <vector>

#include <map>

#include <queue>

#include <stack>

const int MAXN =   + ;

const int INF = 0x7fffffff;

const int MOD = ;

const double ESP = 10e-;

const double Pi = acos(-1.0);

typedef long long LL;

using namespace std;

int a[MAXN];

int bit[MAXN+];

int n;

struct Node{

    int v;

    int order;

    bool operator < (const Node x)const{

        return v < x.v;

    }

};

Node in[MAXN];

int sum(int i){

    int s = ;

    while(i>){

        s += bit[i];

        i -= (i & -i);

    }

    return s;

}

void add(int i,int x){

    while(i <= n){

        bit[i] += x;

        i += (i&-i);

    }

}

int main(){

//    freopen("input.txt","r",stdin);

    while(~scanf("%d",&n) && n){

        memset(bit,,sizeof(bit));

        for(int i = ;i <= n;i++){

            scanf("%d",&in[i].v);

            in[i].order = i;

        }

        sort(in+,in++n);

        for(int i = ;i <= n;i++){

            a[in[i].order] = i;

        }

        LL ans = ;

        for(int i = ;i <= n;i++){

            add(a[i],);

            ans += i-sum(a[i]);

        }

        printf("%lld\n",ans);

    }

    return ;

}

秒客网

poj 2299 逆序数

相关文章