分享一个有意思的问题
给定一个整数序列 \(a_{1}, a_{2}, \cdots, a_{n}\) ，询问至少需要修改多少个元素，可以使得 \(\forall i \in [2, n],\ a_{i} > a_{i - 1}\) 。
有意思的是由整数的离散性，我们可以看出这实际等价于 \(\forall i,\ a_{i} - a_{i - 1} \geq 1\) 。
由偏序的传递性，我们可以看出这实际是 \(\forall 1 \leq j < i \leq n,\ a_{i} - a_{j} \geq i - j\) 。
然后用经典的变量变常量的代数技巧，\(\forall 1 \leq j < i \leq n,\ (a_{i} - i) - (a_{j} - j) \geq 0\) 。
\(\forall i \in [1, n]\) 不妨代数变形 \(b_i = a_i - i\) ，则有 \(\forall 1 \leq j < i \leq n,\ b_{i} - b_{j} \geq 0\) 。
考虑 \(b_1, b_2, \cdots, b_n\) 变成符合条件的序列为 \(c_1, c_2, \cdots, c_n\) ，会存在 \(n\) 排列 \(p\) 的 \(1 \leq k \leq n\) 子排列，满足 \(b_{p_1} = c_{p_1}, b_{p_2} = c_{p_2}, \cdots, b_{p_k} = c_{p_k}\) 不修改，此外都修改。那么答案为 \(n - k\) 。
我们声称 \(k\) 是最大的 \(b\) 序列的 \(LNDS\) 的长度 \(l\) 。显然 \(k \leq l\) ，否则 \(l\) 是假的。
由修改 \(b\) 不违背整数的离散性容易证明 \(k\) 可以取到 \(l\) 。
考虑 \(n - k\) 最小，则 \(k\) 最大，则 \(k = l\) 。