1187. 使数组严格递增

发表于 分类于 阅读次数： Waline： 本文字数： 2.4k 阅读时长 ≈ 8 分钟

考点

  • LIS
  • 贪心

思路

题意

给定数组 \(A=\texttt{arr1}\)，\(B=\texttt{arr2}\)。

允许对 \(A\) 的任意位置执行替换操作：将 \(A[i]\) 替换为 \(B\) 中任意元素（每次替换计 1 次）。

目标是使最终数组严格递增： \[ A[0] < A[1] < \cdots < A[n-1] \] 求最少替换次数；若无解，返回 \(-1\)。

两种设计思路总览

设计一 显式维护“当前前缀最终数组的最后一个值 last”，并记录达到该 last 所需的最小替换次数。

设计二 不直接构造最终数组，而是枚举哪些位置不被替换（称为保留点）。 在相邻保留点之间，用 \(B\) 中的元素整体替换填充，只要该区间可以被合法填满即可。 最大化保留点数量，答案即为 \(n-\text{保留点数}\)。

结构示意

设计一（构造式）

1
2
3
4
5
逐位扫描 A[i]：
  状态： (last -> 最少替换次数)
  转移：
    ├─ 不替换：若 A[i] > last，则 last <- A[i]
    └─ 替换：从 B 中选一个 > last 的值，last <- 选中值

设计二（骨架式）

1
2
3
4
5
6
7
8
9
在 A 上选若干“保留点”（不替换）：
  a0    a1    a2    a3    a4    [∞]
  ^           ^           ^      ^
 保留         保留        保留    保留（哨兵）

两个相邻保留点之间的连续区间：
  必须用 B 中若干个互不相同的值替换，
  并且替换后整体严格递增，
  且落在 (左端值, 右端值) 这个开区间内。

设计一：维护 last → 最小替换次数（前沿 DP）

1. 状态定义

定义： \[ f[i][last] \] 表示处理完前缀 \(A[0..i-1]\) 后，最终数组末尾值为 \(last\) 时的最小替换次数。

初始状态：

  • 前缀为空
  • 设 \(last=-\infty\)
  • 替换次数为 0

2. 转移规则

处理位置 \(i\)，其原始值为 \(A[i]\)。

从每个状态 \((last, cost)\) 出发，有两种选择。

2.1 不替换

若 \[ A[i] > last \] 则可以保留 \(A[i]\)，转移为： \[ f[i+1][A[i]] = \min\bigl(f[i+1][A[i]],\ cost\bigr) \]

2.2 替换（只取刚好大于 last 的最小值）

若选择替换，则需要从 \(B\) 中选一个值 \(x\)，满足： \[ x > last \] 替换一次，代价增加 1。

注意：在固定 last 的情况下，所有替换操作的代价都是一样的（都是 cost+1），因此此时真正影响后续可行性的，只有“替换后的末尾值大小”。

为了给未来留下最大的选择空间，应当选择最小的可行替换值： \[ x = \min\{b \in B \mid b > last\} \] 转移为： \[ f[i+1][x] = \min\bigl(f[i+1][x],\ cost+1\bigr) \]

2.3 为什么替换只取最小可行值

设存在两个可行替换值： \[ last < x_1 < x_2 \] 二者的替换代价相同。

但后续必须满足“下一项大于末尾值”，于是： \[ \{y \mid y > x_2\} \subset \{y \mid y > x_1\} \] 选择更大的 \(x_2\) 只会减少后续可行选择空间，而不会降低替换次数。

因此，\(x_2\) 被 \(x_1\) 严格支配，只保留最小的可行替换值即可。

3. AC代码

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
56
57
58
59
60
class Solution {
public:
    const int maxn = 2e3 + 5, neg = INT_MIN >> 1, inf = INT_MAX >> 1;

    int makeArrayIncreasing(vector<int>& arr1, vector<int>& arr2) {
        // f[i]：处理完 arr1 的前 i 个元素后
        //       key = 当前前缀最终数组的末尾值 last
        //       val = 达到该 last 的最少替换次数
        unordered_map<int, int> f[maxn];

        // st：将 arr2 排序去重后放入 set，便于：
        //     upper_bound(last) 找到 “严格大于 last 的最小可用替换值”
        set<int> st(arr2.begin(), arr2.end());

        int n = arr1.size();

        // 初始：前缀为空，末尾值设为 -∞（用 neg 近似），替换次数为 0
        f[0][neg] = 0;

        // 逐位处理 arr1[i]
        for (int i = 0; i < n; ++i) {
            // 枚举所有可行的末尾值 last 及其最少替换次数
            for (auto& u : f[i]) {
                int last = u.first;
                int cost = u.second;

                // 方案 1：不替换 arr1[i]
                // 条件：必须严格递增，因此要求 last < arr1[i]
                if (last < arr1[i]) {
                    // 更新 f[i+1][arr1[i]] 的最小替换次数
                    f[i + 1][arr1[i]] = f[i + 1].find(arr1[i]) == f[i + 1].end()
                                            ? cost
                                            : min(f[i + 1][arr1[i]], cost);
                }

                // 方案 2：替换 arr1[i]
                // 对固定 last 来说，替换一次的代价恒为 cost+1；
                // 为了给后续留下最大空间，只需选择 “刚好大于 last 的最小值”
                auto it = st.upper_bound(last);
                if (it != st.end()) {
                    int x = *it; // x = nextB(last)

                    // 更新 f[i+1][x] 的最小替换次数
                    f[i + 1][x] = f[i + 1].find(x) == f[i + 1].end()
                                      ? cost + 1
                                      : min(f[i + 1][x], cost + 1);
                }
            }
        }

        // 答案：在所有可能末尾值 last 中取最小替换次数
        int res = inf;
        for (auto& it : f[n]) res = min(res, it.second);

        // 若不可达则返回 -1
        if (res == INT_MAX >> 1) return -1;
        return res;
    }
};

设计二：枚举保留点 + 区间填空判定

1. 从“最少替换”转为“最多保留”

若最终保留 \(K\) 个位置不替换，则： \[ \text{替换次数} = n - K \] 因此问题转化为：最大化保留点数量。

2. 两个保留点之间的可行性判定

设相邻两个保留点分别为 \(j < i\)，其值为 \(A[j]\)、\(A[i]\)

中间需要替换的元素数量为： \[ t = i - j - 1 \] 这些被替换的值必须满足： \[ A[j] < x_1 < x_2 < \cdots < x_t < A[i] \quad,\quad x_k \in B \] 将 \(B\) 排序并去重为： \[ b[0], b[1], \ldots, b[m-1] \] 令： \[ k = \min\{p \mid b[p] \ge A[i]\} \] 即 \(b[0..k-1]\) 都严格小于 \(A[i]\)。

为了尽量降低下界压力，应选择最靠近 \(A[i]\) 的 \(t\) 个数： \[ b[k-t], b[k-t+1], \ldots, b[k-1] \] 因此，区间可被填满的充要条件是：

  1. 数量足够：\(k \ge t\)
  2. 最小的替换值仍大于左端点：

\[ b[k-t] > A[j] \]

3. 哨兵的作用

在数组末尾追加一个 \(+\infty\)

这样最后一个位置必然可以作为保留点，避免对结尾位置单独分类讨论。

4. DP 定义与转移

按“前缀长度”定义状态： \[ f[i] = \text{在前 } i \text{ 个元素中，以 } A[i-1] \text{ 作为保留点结尾的最大保留点数} \] 转移时枚举上一保留点位置 \(j\)，中间替换数为： \[ t = i - j - 1 \]

  • 若 \(j = 0\)：表示左侧没有保留点，只要 \(k \ge i-1\) 即可
  • 若 \(t = 0\)：相邻保留点，只需 \(A[j-1] < A[i-1]\)
  • 若 \(t \ge 1\)：需 \(A[j-1] < A[i-1]\) 且 \(b[k-t] > A[j-1]\)

满足即： \[ f[i] = \max(f[i], f[j] + 1) \] 最终答案为： \[ (n-1) - (f[n] - 1) = n - f[n] \]

5. AC代码

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
class Solution {
public:
    static const int maxn = 2e3 + 5;
    int inf = INT_MAX >> 1, neg = INT_MIN >> 1;

    int makeArrayIncreasing(vector<int>& arr1, vector<int>& arr2) {
        // 将 arr2 排序并去重，后续只使用 arr2[0..m-1]
        sort(arr2.begin(), arr2.end());
        int m = unique(arr2.begin(), arr2.end()) - arr2.begin();

        // 在 arr1 末尾追加 +∞ 哨兵：
        // 使“最后一个位置必作为保留点”成立，统一结尾处理
        arr1.push_back(inf);

        // 令 n 为追加哨兵后的长度
        int f[maxn], n = arr1.size();

        // f[i]（这里 i 是“前缀长度”）：
        // 表示在前 i 个元素中，以 arr1[i-1] 作为“保留点”结尾时，
        // 最多能保留多少个保留点（包含当前这个保留点）
        // 不可达记为 -1
        f[0] = 0; // 空前缀：保留点数为 0

        for (int i = 1; i <= n; ++i) {
            int x = arr1[i - 1]; // 当前保留点候选值

            // it 指向 arr2 中第一个 >= x 的位置
            auto it = lower_bound(arr2.begin(), arr2.begin() + m, x);

            // len = k = # { b < x }，即小于 x 的 arr2 元素个数
            int len = it - arr2.begin();

            f[i] = -1;

            // 枚举上一保留点所在的前缀长度 j（对应值 arr1[j-1]）
            // 中间需要替换的数量 t = i - j - 1
            // 必须满足 t <= len（也就是 i-j-1 <= len），否则小于 x 的 b 数量不够填满
            for (int j = i - 1; i - j - 1 <= len; --j) {
                if (j == 0) {
                    // j==0 表示左侧不存在保留点（相当于 j=-1 的情形）：
                    // 需要把 arr1[0..i-2] 全部替换成 < x 的数
                    // 只要 len >= i-1（由循环条件保证）即可
                    // 此时仅保留当前点，所以保留点数至少为 1
                    f[i] = max(f[i], 1);
                    break;
                }

                // 需要保证保留点严格递增：arr1[j-1] < arr1[i-1]
                // 且上一状态可达：f[j] != -1
                //
                // 若 t=0（即 i==j+1），两保留点相邻，中间无须填空，直接允许；
                // 若 t>=1，需要在 (arr1[j-1], x) 内找到 t 个严格递增的 b：
                // 令 k=len，则最靠近 x 的 t 个分别为 b[k-t..k-1]，
                // 充要条件为 b[k-t] > arr1[j-1]，实现中即 *(it - t) > arr1[j-1]
                if (arr1[i - 1] > arr1[j - 1] && f[j] != -1 &&
                    (i == j + 1 || *(it - (i - j - 1)) > arr1[j - 1])) {

                    // 当前点作为保留点，保留点数 +1
                    f[i] = max(f[i], f[j] + 1);
                }
            }
        }

        // f[n] 对应哨兵位置（含哨兵的保留点数）
        // 原数组长度为 n-1，保留点（不含哨兵）为 f[n]-1
        // 最少替换次数 = (n-1) - (f[n]-1) = n - f[n]
        return f[n] == -1 ? -1 : n - 1 - (f[n] - 1);
    }
};

思考题（变形）

问题

允许将 \(A[i]\) 替换为任意整数，求最少替换次数使数组严格递增。

推导

严格递增意味着相邻至少增加 1，因此对任意 \(i > j\)： \[ A[i] \ge A[j] + (i - j) \] 等价于： \[ A[i] - i \ge A[j] - j \] 定义新数组： \[ B[i] = A[i] - i \] 则原问题等价于：使 \(B\) 非递减。

最大可保留位置数量等于 \(B\) 的最长非递减子序列长度，记为 LNDS；

最少替换次数为： \[ n - \text{LNDS} \]

样例说明

给定： \[ A = [1,2,2,3] \] 其最长严格递增子序列长度为 3，但要使整个数组严格递增，至少需要替换 2 个数。

原因在于严格递增不仅要求数值递增，还隐含了“下标间隔必须对应至少 1 的增量”这一约束。

通过变换 \(B[i]=A[i]-i\)，该约束被吸收进数值中，从而转化为普通的非递减判定，LNDS 才能给出正确答案。