HDU1394-Minimum Inversion Number(逆序对+权值线段树)

题目链接: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;
}

发表留言

人生在世,错别字在所难免,无需纠正。