您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

HDU 1394 Minimum Inversion Number：線段樹求逆序數與循環移位優化

編輯：C++ 入門

題目模型

HDU 1394：給定 0..N-1 的排列（N ≤ 5000），可將首元素移至尾部（循環左移）。求所有循環移位中逆序數的最小值。

線段樹求初始逆序數

維護「值是否已出現」的頻率線段樹。掃描陣列 a[i]，查詢 [a[i]+1, N-1] 區間和即為以 a[i] 為左端點的逆序對數，累加得初始逆序數 inv0。

循環移位遞推公式

將首元素 x = a[0] 移至尾部：

減少的逆序數：原本在 x 後面且 < x 的元素個數 = x（因為是 0..N-1 排列）
增加的逆序數：原本在 x 前面且 > x 的元素個數 = N-1-x
新逆序數 = old + (N-1-x) - x = old + N-1-2x

依次套用公式即可 O(N) 算出所有移位的逆序數，取最小值。

完整 AC 程式碼

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 5005;
int sum[MAXN<<2], a[MAXN];

void build(int rt, int l, int r) {
    sum[rt] = 0;
    if (l == r) return;
    int mid = (l+r)>>1;
    build(rt<<1, l, mid);
    build(rt<<1|1, mid+1, r);
}

void update(int rt, int l, int r, int pos) {
    if (l == r) { sum[rt]++; return; }
    int mid = (l+r)>>1;
    if (pos <= mid) update(rt<<1, l, mid, pos);
    else update(rt<<1|1, mid+1, r, pos);
    sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}

int query(int rt, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return sum[rt];
    int mid = (l+r)>>1, ans = 0;
    if (ql <= mid) ans += query(rt<<1, l, mid, ql, qr);
    if (qr > mid) ans += query(rt<<1|1, mid+1, r, ql, qr);
    return ans;
}

int main() {
    int n;
    while (scanf("%d", &n) == 1) {
        build(1, 0, n-1);
        int inv = 0;
        for (int i = 0; i < n; ++i) {
            scanf("%d", &a[i]);
            inv += query(1, 0, n-1, a[i], n-1);
            update(1, 0, n-1, a[i]);
        }
        int ans = inv;
        for (int i = 0; i < n; ++i) {
            inv += n - 1 - 2*a[i];
            ans = min(ans, inv);
        }
        printf("%d\n", ans);
    }
    return 0;
}