HDU 5256 序列變換：LIS 變形求最少修改次數

題目大意

給定長度為 N 的正整數序列，允許修改任意元素為任意整數，求使序列變為嚴格遞增的最少修改次數。多組測試數據，N ≤ 10^5，元素值 ≤ 10^6。

解題思路

最少修改次數 = N - 最長不需修改的子序列長度。對於嚴格遞增序列，保留下標 i 和 j (i < j) 的元素不變，需滿足 a[j] - a[i] > j - i，即 a[j] - j > a[i] - i。因此將原序列轉換為 b[i] = a[i] - i，問題轉化為求 b 序列的最長非嚴格遞增子序列 (LNDS) 長度。使用 O(N log N) 的貪心 + 二分法維護 LNDS 即可。

代碼 (C++)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 100005;
int a[MAXN], b[MAXN];

int findPos(int len, int val) { // 找第一個大於 val 的位置 (上界)
    int l = 1, r = len, mid;
    while (l <= r) {
        mid = (l + r) >> 1;
        if (b[mid] <= val) l = mid + 1;
        else r = mid - 1;
    }
    return l;
}

int main() {
    int T; scanf("%d", &T);
    for (int cas = 1; cas <= T; cas++) {
        int n; scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        int len = 0;
        for (int i = 1; i <= n; i++) {
            int val = a[i] - i;
            int pos = findPos(len, val);
            b[pos] = val;
            if (pos > len) len++;
        }
        printf("Case #%d:\n%d\n", cas, n - len);
    }
    return 0;
}