修改数组「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
#include
#include
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 > &＃39;9&＃39; || ch <&＃39;0&＃39;) {
if (ch == &＃39;-&＃39;) flag = -1;
ch = getchar();
}
while (ch <= &＃39;9&＃39; && ch >= &＃39;0&＃39;) {
ret = (ret <<3) + (ret <<1) + (ch ^ &＃39;0&＃39;);
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;
}