ACM模版

描述

题解

题意一开始没看懂，懵了许久，而后了解到，一个由 0~n-1 组成的序列，每次都可以把队首的元素移动到队尾，求形成的 n 个序列中最小逆序对数目。

这个问题简化看来就是求逆序数，先求原始状况逆序数，其他可以递推出来，假设初始序列逆序数个数为 N 个，那么将序列首放到序列尾，逆序数会减少 A[i] 个，然后另外增加 N-(A[i]+1) 个，枚举所有状态，获取最优解即可。

所以问题的关键只剩下第一个如何求逆序数，方法有很多，因为 n 比较小，所以可以暴力，高效一些的方法也有，线段树可解，当然，求逆序数比较常用的方法还是要数归并排序求逆序数了，一个模板解决。鉴于最近在做线段树专项训练，所以用线段树解了一下下，结点插入，区间求和~~~

代码

#include <iostream>
#include <cstdio>

using namespace std;

const int MAXN = 5555;

int sum[MAXN << 2];

void pushUp(int root)
{
    sum[root] = sum[root << 1] + sum[root << 1 | 1];
}

void build(int root, int l, int r)
{
    sum[root] = 0;

    if (l == r)
    {
        return ;
    }
    int m = (l + r) >> 1;
    build(root << 1, l, m);
    build(root << 1 | 1, m + 1, r);
}

void update(int root, int val, int l, int r)
{
    if (l == r)
    {
        sum[root]++;
        return ;
    }

    int m = (l + r) >> 1;
    if (val <= m)
    {
        update(root << 1, val, l, m);
    }
    else
    {
        update(root << 1 | 1, val, m + 1, r);
    }
    pushUp(root);

}

int query(int L, int R, int l, int r, int root)
{
    if (L <= l && r <= R)
    {
        return sum[root];
    }

    int m = (l + r) >> 1;
    int ret = 0;
    if (L <= m)
    {
        ret += query(L, R, l, m, root << 1);
    }
    if (R > m)
    {
        ret += query(L, R, m + 1, r, root << 1 | 1);
    }
    return ret;
}

int A[MAXN];

int main(int argc, const char * argv[])
{
    int n;

    while (~scanf("%d", &n))
    {
        build(1, 0, n - 1);
        int sum = 0;
        for (int i = 0; i < n; i++)
        {
            scanf("%d", A + i);
            sum += query(A[i], n - 1, 0, n - 1, 1);
            update(1, A[i], 0, n - 1);
        }
        int ret = sum;
        for (int i = 0; i < n; i++)
        {
            sum += n - A[i] - A[i] - 1;
            ret = min(ret, sum);
        }

        printf("%d\n", ret);
    }

    return 0;
}