hdu - 4911 - Inversion（離散化+樹狀數組）

hdu - 4911 - Inversion（離散化+樹狀數組）

題意：一個由n個非負整數組成的序列，問進行最多k次相鄰交換後最少的逆序對數 (1 ≤ n ≤ 10^5, 0 ≤ k ≤ 10^9, 0 ≤ ai ≤ 10^9)。。

題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=4911

——>>每次只能交換相鄰的兩個數，每次交換，只改變這兩個數的逆序，其他的數對於這兩個數的逆序沒有改變，所以，求出所有的逆序對，再減去k就是答案。

#include 
#include 
#include 

using namespace std;

const int MAXN = 100000 + 10;

int n, k;
int a[MAXN], b[MAXN];
long long C[MAXN];

void Init()
{
    memset(C, 0, sizeof(C));
}

void Read()
{
    for (int i = 0; i < n; ++i)
    {
        scanf("%d", a + i);
    }
}

int Lowbit(int x)
{
    return x & (-x);
}

long long Sum(int x)
{
    long long nRet = 0;

    while (x > 0)
    {
        nRet += C[x];
        x -= Lowbit(x);
    }

    return nRet;
}

void Add(int x)
{
    while (x <= n)
    {
        C[x]++;
        x += Lowbit(x);
    }
}

void Solve()
{
    int nCnt = 0;
    int nId = 0;
    long long nReverse = 0;

    memcpy(b, a, sizeof(a));
    sort(b, b + n);
    nCnt = unique(b, b + n) - b;

    for (int i = n - 1; i >= 0; --i)
    {
        nId = lower_bound(b, b + nCnt, a[i]) - b + 1;
        nReverse += Sum(nId - 1);
        Add(nId);
    }

    if (nReverse > k)
    {
        nReverse -= k;
    }
    else
    {
        nReverse = 0;
    }

    printf("%I64d\n", nReverse);
}

int main()
{
    while (scanf("%d%d", &n, &k) == 2)
    {
        Init();
        Read();
        Solve();
    }
    return 0;
}