修改数组「NOIP多校联考 2019」

【题目描述】
给出一个整数数组 \(A\)，你可以将任何一个数修改为任意一个正整数，最终使得整个数组是严格递增的且均为正整数。问最少需要修改几个数？

【输入格式】
第 \(1\) 行：一个数 \(N\) 表示序列的长度(\(1\leq N\leq 100000\))。
第 \(2\) ~ \(N+1\) 行：每行 \(1\) 个数，对应数组元素。(\(0\leq A[i]\leq 10^9\))。

【输出格式】
输出最少需要修改几个数使得整个数组是严格递增的。

题解
如果把题目改成 “最终使得整个数组是不下降的” 似乎就会好做很多
把严格递增的数组改为不降的数组也很简单 把每个\(A[i]\)变成\(A[i]-i\)就行了

这样处理后 原题就变成将处理后的数组修改成不下降数组最少修改几个数
求一下它的最长不下降子序列 然后把其他数改掉就行了
LIS不会求？点这里

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;

ll n;
ll a[100005], b[100005], sz;
ll num[100005], len;
ll maxn;

ll read() {
    ll ret = 0, flag = 1;
    char ch = getchar();
    while (ch > '9' || ch < '0') {
        if (ch == '-') flag = -1;
        ch = getchar();
    }
    while (ch <= '9' && ch >= '0') {
        ret = (ret << 3) + (ret << 1) + (ch ^ '0');
        ch = getchar();
    }
    return ret * flag;
}

ll search(ll x) {
    ll l = 1, r = sz, mid, ret = 0;
    while (l <= r) {
        mid = (l + r) >> 1;
        if (b[mid] > x) {
            ret = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return ret;
}

int main() {
    n = read();
    for (int i = 1; i <= n; i++) {
        a[i] = read() - i;
    }
    for (int i = 1; i <= n; i++) {
        if (a[i] >= 0) num[++len] = a[i];
    }
    for (int i = 1; i <= len; i++) {
        if (num[i] >= b[sz]) b[++sz] = num[i];
        else b[upper_bound(b + 1, b + sz + 1, num[i]) - b] = num[i];
        maxn = max(sz, maxn);
    }
    printf("%lld\n", n - maxn);
    return 0;
}