AK-dream

【题目描述】
给出一个整数数组 $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不会求?点这里

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#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;
}


 评论