HDU 1394 Minimum Inversion Number（线段树求最小逆序数对）

ACM

题意：

给一个序列由[1,N]构成。能够通过旋转把第一个移动到最后一个。

问旋转后最小的逆序数对。

分析：

注意，序列是由[1,N]构成的，我们模拟下旋转，总的逆序数对会有规律的变化。

求出初始的逆序数对再循环一遍即可了。

至于求逆序数对，我曾经用归并排序解过这道题：点这里。

只是因为数据范围是5000。所以全然能够用线段树或树状数组来做：求某个数的作为逆序数对的后面部分的对数，能够在前面的数中查询小于这个数的数的个数。

直接在线一边加一边查即可了，复杂度为O(nlogn)。

只是老实说，这题的单个数没有太大，不然线段树和树状数组都开不下的。所以求逆序数对的最佳算法应该是归并排序解。

代码：

/*

*  Author:      illuz <iilluzen[at]gmail.com>

*  Blog:        http://blog.csdn.net/hcbbt

*  File:        1394_segment_tree.cpp

*  Create Date: 2014-08-05 10:08:42

*  Descripton:  segment tree

*/

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

#define repf(i,a,b) for(int i=(a);i<=(b);i++)

#define lson(x) ((x) << 1)

#define rson(x) ((x) << 1 | 1)

typedef long long ll;

const int N = 5010;

const int ROOT = 1;

// below is sement point updated

struct seg {

    ll w;

};

struct segment_tree {

    seg node[N << 2];

    void update(int pos) {

        node[pos].w = node[lson(pos)].w + node[rson(pos)].w;

    }

    void build(int l, int r, int pos) {

        if (l == r) {

            node[pos].w = 0;

            return;

        }

        int m = (l + r) >> 1;

        build(l, m, lson(pos));

        build(m + 1, r, rson(pos));

        update(pos);

    }

    // add the point x with y

    void modify(int l, int r, int pos, int x, ll y) {

        if (l == r) {

            node[pos].w += y;

            return;

        }

        int m = (l + r) >> 1;

        if (x <= m)

            modify(l, m, lson(pos), x, y);

        else

            modify(m + 1, r, rson(pos), x, y);

        update(pos);

    }

    // query the segment [x, y]

    ll query(int l, int r, int pos, int x, int y) {

        if (x <= l && r <= y)

            return node[pos].w;

        int m = (l + r) >> 1;

        ll res = 0;

        if (x <= m)

            res += query(l, m, lson(pos), x, y);

        if (y > m)

            res += query(m + 1, r, rson(pos), x, y);

        return res;

    }

    // remove the point that the sum of [0, it] is x, return its id

    int remove(int l, int r, int pos, ll x) {

        if (l == r) {

            node[pos].w = 0;

            return l;

        }

        int m = (l + r) >> 1;

        int res;

        if (x < node[lson(pos)].w)

            res = remove(l, m, lson(pos), x);

        else

            res = remove(m + 1, r, rson(pos), x - node[lson(pos)].w);

        update(pos);

        return res;

    }

} sgm;

int n, a[N], b[N], t, sum, mmin;

int main() {

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

        sgm.build(1, n, ROOT);

        sum = 0;

        repf (i, 1, n)

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

        for (int i = n; i >= 1; i--) {

            b[i] = sgm.query(1, n, ROOT, 1, a[i] + 1);

            sum += b[i];

            sgm.modify(1, n, ROOT, a[i] + 1, 1);

        }

        mmin = sum;

        repf (i, 1, n) {

            sum = sum - a[i] + (n - 1 - a[i]);

            mmin = min(mmin, sum);

        }

        cout << mmin << endl;

    }

    return 0;

}