题目链接：HDU1394-Minimum Inversion Number

题意：

n个数，要求求出一个排列，使其逆序对数最少。

题解：

根据样例，最开始的序列为：1,3,0,2，逆序对数为3。

如果把1放到最后变为：3,0,2,1，逆序对数为4。

因为1放到最后，少了(1,0)这组逆序对，多了(3,1),(2,1)这两组逆序对。

所以归纳可得，当我们把a[i]放到最后时，会减少（a[i]）组逆序对，增加（n-a[i]-1）组逆序对数。

所以，我们就可以用归并排序，树状数组，线段树等求出逆序对数即可。

参考代码：

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e3 + 3;
int n;
int a[MAXN];
int sum[MAXN << 2];
void pushup(int rt)
{
    sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}
void build(int l, int r, int rt)
{
    if (l == r)
    {
        sum[rt] = 0;
        return;
    }
    int mid = (l + r) >> 1;
    build(l, mid, rt << 1);
    build(mid + 1, r, rt << 1 | 1);
    pushup(rt);
}
void update(int p, int val, int l, int r, int rt)
{
    if (l == r)
    {
        sum[rt] = 1;
        return;
    }
    int mid = (l + r) >> 1;
    if (p <= mid)
        update(p, 1, l, mid, rt << 1);
    else if (p > mid)
        update(p, 1, mid + 1, r, rt << 1 | 1);
    pushup(rt);
}
int query(int L, int R, int l, int r, int rt)
{
    if (L > R)
        return 0;
    if (L <= l && r <= R)
        return sum[rt];
    int mid = (l + r) >> 1;
    int res = 0;
    if (L <= mid)
        res += query(L, R, l, mid, rt << 1);
    if (R > mid)
        res += query(L, R, mid + 1, r, rt << 1 | 1);
    return res;
}
int main()
{
    while (scanf("%d", &n) == 1)
    {
        int tot = 0;
        build(1, n, 1);
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &a[i]);
            a[i]++;
            tot += query(a[i] + 1, n, 1, n, 1);
            update(a[i], 1, 1, n, 1);
        }
        int ans = tot;
        for (int i = 1; i <= n; i++)
        {
            tot += (n - a[i] - a[i] + 1);
            ans = min(ans, tot);
        }
        printf("%d\n", ans);
    }
    return 0;
}