2111. 使数组 K 递增的最少操作次数

发表于 2025-12-24 分类于力扣阅读次数： Waline：本文字数： 1.1k 阅读时长 ≈ 4 分钟

考点

最长单调不减序列

思路

——建模思路与最长单调不减子序列（LNDS）转化

1. 问题重述（Problem Restatement）

给定一个长度为 \(n\) 的数组 \[ \text{arr} = [a_0, a_1, \dots, a_{n-1}] \] 以及一个正整数 \(k\)。

称数组是 k-递增（k-increasing） 的，当且仅当对所有 \[ i \in [0, k-1] \] 序列 \[ a_i, a_{i+k}, a_{i+2k}, \dots \] 是非递减的（即允许相等）。

一次操作可以将数组中的任意一个元素修改为任意值。目标是：最少修改多少次，使数组变为 k-递增。

2. 同余分组建模（Residue Class Decomposition）

2.1 按下标同余类拆分

注意到 k-递增的定义完全按下标模 \(k\) 独立：

对每个固定的 \(i\)，只要求 \[ a_i \le a_{i+k} \le a_{i+2k} \le \cdots \]
不同 \(i\) 之间互不影响

因此，可以将原问题拆分为 \(k\) 个相互独立的子问题：

对于每个 \(i \in [0, k-1]\)，使序列 \[ S_i = \{a_i, a_{i+k}, a_{i+2k}, \dots\} \] 变为非递减序列，并最小化修改次数。

最终答案即为所有子问题答案之和： \[ \text{Answer} = \sum_{i=0}^{k-1} \text{cost}(S_i) \]

3. 子问题的本质：最少修改使序列非递减

3.1 等价转化的核心思想

考虑一个固定子序列： \[ S = [x_1, x_2, \dots, x_m] \] 目标是：

最少修改多少个元素，使整个序列非递减。

这是一个经典等价问题：

最少修改次数 = 序列长度 − 最长“可保留”的非递减子序列长度

原因如下。

3.2 为什么可以转化为 LNDS？

结论（Key Claim）

对于任意序列 \(S\)： \[ \boxed{ \text{最少修改次数} = |S| - \text{LNDS}(S) } \] 其中 LNDS 表示 最长非递减子序列（Longest Non-Decreasing Subsequence）。

证明思路（直观版）

保留子序列，其余修改
- 设已经选定一个非递减子序列，其长度为 \(L\)
- 可以保持这 \(L\) 个元素不变
- 其余 \(|S| - L\) 个元素，全部通过修改“填补”到合适的值
不可能保留超过 LNDS
- 若试图保留更多元素不修改
- 则这些元素本身必须构成一个非递减子序列
- 与 LNDS 的定义矛盾

因此：

最多能保留的元素数 = LNDS
最少需要修改的元素数 = 总长度 − LNDS

3.3 为什么是“非递减”而不是“严格递增”？

题目要求的是： \[ a_i \le a_{i+k} \] 允许相等，因此对应的是：

Longest Non-Decreasing Subsequence
而不是 LIS（严格递增）

在实现中，这正对应于使用：

1	upper_bound

而非 lower_bound。

4. LNDS 的贪心 + 二分求法

4.1 维护“结尾最小值”数组

使用经典 patience sorting 思想：

维护数组 f
f[t] 表示：

长度为 \(t+1\) 的非递减子序列，其最小可能结尾值

遍历序列中的每个元素 x：

找到最小的 pos，使得： \[ f[pos] > x \]
用 x 替换 f[pos]
若不存在这样的 pos，则在末尾追加

这一步正是：

1	upper_bound(f.begin(), f.end(), x)

4.2 正确性要点

f 始终保持非递减
f.size() 始终等于当前扫描前缀的 LNDS 长度
每次替换只会让“结尾更优”，不影响可行性

时间复杂度： \[ O(m \log m) \] 其中 \(m\) 是子序列长度。

5. 总体算法流程

按下标对 \(k\) 取模，划分为 \(k\) 个子序列
对每个子序列：
- 求其 LNDS 长度
- 累加 子序列长度 − LNDS
返回总和

总体复杂度： \[ O(n \log (n/k)) \subseteq O(n \log n) \]

6. AC代码

6.1 使用 STL `upper_bound`

class Solution {
public:
    static const int maxn = 1e5 + 5;
    int kIncreasing(vector<int>& arr, int k) {
        int ans = 0, n = arr.size();
        for (int i = 0; i < k; ++i) {
            vector<int> f;
            int len = 0;
            for (int j = i; j < n; j += k) {
                len++;
                auto it = upper_bound(f.begin(), f.end(), arr[j]);
                if (it == f.end())
                    f.push_back(arr[j]);
                else
                    *it = arr[j];
            }
            ans += len - f.size();
        }
        return ans;
    }
};

6.2 手写二分版本

class Solution {
public:
    static const int maxn = 1e5 + 5;
    int find(vector<int>& arr, int k) {
        int l = 0, r = arr.size();
        while (l < r) {
            int mid = (l + r) >> 1;
            if (arr[mid] > k)
                r = mid;
            else
                l = mid + 1;
        }
        return l;
    }
    int kIncreasing(vector<int>& arr, int k) {
        int ans = 0, n = arr.size();
        for (int i = 0; i < k; ++i) {
            vector<int> f;
            int len = 0;
            for (int j = i; j < n; j += k) {
                len++;
                int idx = find(f, arr[j]);
                if (idx == f.size())
                    f.push_back(arr[j]);
                else
                    f[idx] = arr[j];
            }
            ans += len - f.size();
        }
        return ans;
    }
};

考点

思路