「BZOJ 1831」「AHOI 2008」逆序对「贪心」

题意

给定一个长度为\(n\)，值域为\([1,k]\)，某些位置不确定的数组，求最小的逆序对。\(n\leq 10^4, k \leq 100\)

题解

这题有人用前缀和优化\(dp\)过了，但是这里还是讲一种逐一填的做法

首先证明：填进去的数一定是单调不减的，换句话说不构成逆序对。证明很简单，因为假设在\(i\)，\(j\)两处（\(i < j\)），填进去的数构成逆序对，交换这\(i, j\)，不影响\([1, i - 1],[j + 1, n]\)的逆序对，对于\([i + 1, j - 1]\)来说逆序对减少或不变，并且\(i,j\)构成的逆序对消失。

所以我们只要考虑已经填好的数。每次找到一个贡献最小的\(k\)填就行了。

我用树状数组维护了一下，实际上直接数组也可以。

#include <algorithm>

#include <cstdio>

using namespace std;

const int N = 1e4 + 10;

int n, k, a[N], bit[2][N];

void add(int z, int x, int y) {

    for(; x <= k; x += x & (-x)) bit[z][x] += y;

}

int qry(int z, int x) {

    int ans = 0;

    for(; x >= 1; x &= x - 1) ans += bit[z][x];

    return ans;

}

int main() {

    scanf("%d%d", &n, &k);

    for(int i = 1; i <= n; i ++) {

        scanf("%d", a + i);

        if(~ a[i]) add(1, a[i], 1);

    }

    int ans = 0;

    for(int i = 1; i <= n; i ++) {

        if(a[i] == -1) {

            int x = 1, y = n << 1;

            for(int j = 1; j <= k; j ++) {

                int s = qry(0, k) - qry(0, j) + qry(1, j - 1);

                if(s < y) y = s, x = j;

            }

            a[i] = x;

            add(0, a[i], 1);

        } else add(0, a[i], 1), add(1, a[i], -1);

        ans += qry(0, k) - qry(0, a[i]);

    }

    printf("%d\n", ans);

    return 0;

}

巴特西

「BZOJ 1831」「AHOI 2008」逆序对「贪心」

最新文章

热门文章