HDU 5256 序列變換：LIS 求最少修改數（同 3970）

題目

同 HDU 5256：修改最少元素使序列嚴格遞增。N ≤ 10^5。

解法

嚴格遞增 ⇔ 保留下標 i,j (ia[j]-a[i] > j-i ⇔ (a[j]-j) > (a[i]-i)。
令 b[i] = a[i] - i，求 b 的最長非降子序列 (LNDS) 長度 L。答案 = n - L。
O(n log n) 貪心 + 二分維護 LNDS：遍歷 b[i]，在單調隊列中找第一個 > b[i] 的位置替換，若全 ≤ 則 Append。

代碼 (C++)

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100010;
int b[MAXN];
int findPos(int len, int val) { // 返回第一個 > val 的位置 (1-based)
    int l = 1, r = len;
    while (l <= r) {
        int 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);
        int len = 0;
        for (int i = 1; i <= n; i++) {
            int a; scanf("%d", &a);
            int val = a - i;
            int pos = findPos(len, val);
            b[pos] = val;
            if (pos > len) len++;
        }
        printf("Case #%d:\n%d\n", cas, n - len);
    }
    return 0;
}