HDU 1394 - Minimum Inversion Number

题目描述

Minimum Inversion Number

解法：树状数组（C++）

#include <bits/stdc++.h>using namespace std;const int N = 5005;
int c[N];
int a[N];int lowbit(int x){
    return x&(-x);}void update(int x)
{
    while(x<N){
    c[x]++;x += lowbit(x);}
}int sum(int x)
{
    int s = 0;while(x>0){
    s += c[x];x -= lowbit(x);}return s;
}int main()
{
    int n;while(~scanf("%d", &n)){
    memset(c, 0, sizeof(c));int cnt = 0;for(int i=1;i<=n;i++){
    scanf("%d", &a[i]);a[i]++; // 样例中出现了为0的元素，而我们希望a[..]数组中的元素时从1开始的，故对每个输入元素都进行加1操作cnt += sum(N-1)-sum(a[i]); // 求比a[i]大的元素的个数，即a[i]的逆序数update(a[i]);}int mmin = INT_MAX;for(int i=1;i<=n;i++){
    // 数组每发生一次，逆序对数减少a[i]，但同时增加 n- a[i] - 1// 例如 3 6 9 0 8 5 7 4 2 1 把3移到后面，则它的逆序数会减少3（0 2 1），但同时增加6cnt = cnt-(a[i]-1)+(n-a[i]);mmin = min(mmin, cnt);}printf("%d\n", mmin);}return 0;
}