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