在《信息学奥赛一本通·高手训练》里刷到编号1680的“序列”时我其实是被题面短小精悍的样貌骗进来的。题目只说小a手上有一个包含n个正整数的序列每次可以花1个金币做一次操作却没说清楚操作是什么。我按训练册配套题面上最常见的模型来理解一次操作就是把任意一个元素拎出来再插到任意一个位置目标是让整个序列变成严格递增的1,2,...,n问最少需要多少个金币。这个模型在算法竞赛里属于“看起来是贪心其实考的是序列结构”的典型题网上也有人用“最少移动次数使序列有序”来归类它。能把这道题吃透至少等于学会了三件事怎么把一个操作问题转化成结构问题、怎么证明答案的下界、以及最长上升子序列LIS为什么能在一堆序列题里反复出现。这篇文章我会从零开始拆题介绍O(n log n)的完整做法顺便把我在本地调试和比赛时踩过的几个坑一起写出来。1. 题目到底在考什么——从“移动谁”到“保留谁”1.1 把题面翻译成人话如果题目只是说“移动元素”那第一步一定是确定这个操作到底等价于什么。假设序列是 [3, 1, 2, 5, 4]目标是 [1, 2, 3, 4, 5]。一次移动可以把3直接拿到1后面得到 [1, 3, 2, 5, 4]也可以先把5插到4后面……操作路径非常多直接搜索是不可行的因为哪怕n只有15状态数也爆炸。所以要跳出来看与其想“我该移动谁”不如想“我可以让谁待在原地不动”。这个视角的转变是这道题最重要的突破口。既然每次移动都会改变元素间的相对位置那些从头到尾都不动、在原序列里就已经排好相对顺序的元素自然形成了一个不需要花钱的子序列。而因为这个子序列最终要存在于一个递增的有序序列里它在数值上也必须是严格递增的——它们的相对顺序没错数值也递增就完全不用动。剩下的每一个元素都至少花一个金币把它插回正确位置。这里要注意题目说的是“任意一个元素移动到任意位置”这是一个很强力的操作。它和“交换相邻元素”“任意交换两个元素”都不太一样。移动一个元素到任意位置等价于把这个元素从原来的序列里抽走然后插到某个空档里唯一不会被动到的就是那些没被抽走的元素。所以解题核心就变成了选出一个尽可能长的子序列保留下来其他元素各花一次操作插回去。1.2 为什么答案是 n 减去 LIS这个思路可以严格化。假设我们能让某个子序列保持不动这个子序列必须满足两个条件在原序列中的下标递增同时数值严格递增。换句话说它就是原序列的一个严格上升子序列。如果保留了这个长度为L的上升子序列其它n-L个元素通过一次移动插进对应的空缺位置整个序列就能有序所以答案最多是 n-L。反过来任何一个可行解里没花钱的那些元素在原序列中保持了相对顺序最终也落在正确的递增位置上它们一定构成一个上升子序列。假设最优解里不动元素的数量是K那么K不可能超过原序列LIS的长度。所以最少花费的下界是 n-LIS而构造方案又正好能达到这个下界答案就是 n 减去 LIS 长度。可能有人会问为什么不动的子序列应该选LIS里具体哪一条答案是这条题只需要长度不需要方案。因为无论选哪一条长度为LIS的上升子序列剩下的元素数量都是 n-LIS都能通过每次移动一个数的方式排好。你不需要在代码里还原移动路径只需要算出LIS长度。1.3 动手模拟一组数据用 [3, 1, 2, 5, 4] 来推它的LIS长度是多少最长上升子序列可以是 [1, 2, 5] 或 [1, 2, 4]长度都是3。所以答案应该是 5-32。怎么用2次移动完成排序可以保留 [1, 2, 4]把3插到1后面把5插到4后面两次移动就得到 [1, 2, 3, 4, 5]。这个例子也说明答案不等于“最长连续上升子序列”。LIS允许中间跨过几个被移动的元素千万别把“连续”两个字想当然地带进去。很多人第一次做会误以为要找最长连续上升段那是比较经典的误区。实际上连续段只是LIS的一个特例保留不连续但数值递增的子序列往往能留下更多的元素花费也就更少。2. 核心前置知识LIS的两种求法2.1 朴素动态规划适合n不超过几千的版本先把最朴素的O(n^2) DP写在前面虽然这道题大概率数据范围很大但理解它才能理解优化版本。定义 dp[i] 表示以第 i 个数结尾的最长上升子序列长度初始化 dp[i] 1。对每个 i枚举前面的 j如果 a[j] a[i]就用 dp[j]1 更新 dp[i]。转移方程是 dp[i] max(dp[i], dp[j]1)。最终答案取所有 dp[i] 的最大值。这个做法在 n5000 时还能跑n1e5 就不行了。一本通高手训练这种数据范围通常都要求优化所以这个朴素版本更多是作为“思路锚点”存在而不是最终AC方案。2.2 贪心加二分从O(n^2)到O(n log n)优化的关键在于维护一个 d 数组。我习惯把 d[len] 解释成当前已经扫过元素中长度为 len 的严格上升子序列的末尾元素的最小可能值。d 本身一定是严格递增的。扫描到新元素 x 时如果 x 比 d 里所有数都大就说明它可以接到一个更长的子序列后面直接 push_back否则用 x 去替换 d 中第一个大于等于 x 的位置也就是 lower_bound(d.begin(), d.end(), x)。这里为什么用 lower_bound因为我们要严格上升x 不能覆盖等于自己的值否则会破坏严格性所以找的是第一个不小于 x 的位置。改小这个位置上的末尾值相当于同样长度下保留更小的尾巴为后续更长序列创造空间。如果题目要求非降子序列就把 lower_bound 改成 upper_bound这一字之差是很多同学翻车的根源。2.3 用 d 数组模拟一次完整扫描给一组数据 [4, 8, 9, 5, 6, 7]读到4d [4] 读到8d [4, 8] 读到9d [4, 8, 9] 读到5lower_bound 找到8替换d [4, 5, 9] 读到6lower_bound 找到9替换d [4, 5, 6] 读到77 比 6 大pushd [4, 5, 6, 7]LIS长度为4。这个过程不需要真正找出是哪4个元素但长度已经正确。如果此时再多一个3d 会变成 [3, 5, 6, 7]长度还是4但整个数组被压得更紧凑后面的数字更容易接上去。这其实就是贪心思想相同长度下尽量保留更小的末尾值。可以把它类比成打牌时的“替换手牌”——手里牌长度不变但把大牌换成小牌后面的牌才更容易上接。3. 完整设计与C17实现3.1 从题目到程序的设计流程整体流程可以分成四步第一步读入 n 和数组 a第二步计算LIS长度第三步输出 n-lis第四步……没有了。对核心实现就这么短但每一步都有值得注意的细节。读入方面如果 n 到 1e5 或 1e6建议用 scanf 或者自己封装一个快速读入函数不要直接 cin除非做了 ios::sync_with_stdio(false) 和 cin.tie(nullptr)。计算LIS时用一个 vector d 来维护提前 reserve(n) 可以减少扩容开销。返回的 d.size() 就是答案需要的 len。3.2 完整可参考的C17代码直接上一份我调试好的C17代码#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorint a(n); for (int i 0; i n; i) { cin a[i]; } vectorint d; d.reserve(n); for (int x : a) { auto it lower_bound(d.begin(), d.end(), x); if (it d.end()) { d.push_back(x); } else { *it x; } } cout n - (int)d.size() \n; return 0; }这段代码的核心只有那个循环。x 是当前读到的数lower_bound 在 d 中找到第一个不小于 x 的位置。如果找不到就说明 x 能延长当前最长骨架否则用 x 替换那个位置的旧值。最后 d.size() 就是LIS长度输出 n 减它即可。例如输入5 3 1 2 5 4程序会输出 2。输入 6 和 1 2 3 4 5 6LIS长度6输出0因为序列已经有序一个金币都不用花。输入 6 和 6 5 4 3 2 1LIS长度1输出5——这符合直觉每次只能移动一个元素完全逆序的排列至少要动 5 个元素才能排成 1 到 6。3.3 复杂度与数据范围这个算法的时间复杂度是 O(n log n)空间复杂度 O(n)。一本通里很多序列类题目的 n 可以开到 1e5 甚至 1e6O(n log n) 都能扛住。如果是 n1e6注意 vector 的 reserve以及使用更快的读入。我在本地跑过 1e6 随机排列不开O2优化大概0.2秒到0.4秒开O2会更快完全不需要担心。而同样数据量如果写 O(n^2) 的DP1e12量级的运算可能几分钟都跑不完所以优化不是锦上添花是能否AC的关键。顺带提一句如果 n 很大输出答案时可以把减法结果存成 long long虽然一般 int 也够但多写一步没坏处。4. 常见问题与排查技巧实录4.1 把“移动到任意位置”误解成“相邻交换”这类题最大的坑是审题。如果变成“每次只能交换相邻两个元素”答案就是逆序对数量不是 n-LIS。逆序对数量可能远大于 n-LIS。比如 [5,4,3,2,1]相邻交换需要10次而移动到任意位置只需要4次。网上不少讨论区把这两种模型混在一起导致越看越乱。拿到题目先确认操作定义再选算法模型。我自己的习惯是把三种常见操作写成一个对照表贴在笔记里操作类型典型问题核心解法移动到任意位置序列变升序最少移动次数n - LIS长度交换相邻两个元素冒泡排序最少交换次数逆序对数量任意交换两个元素排列排序最少交换次数n - 置换环数每次做题前先圈出“操作动词”再决定套哪套解法。这个习惯帮我避开了很多无谓的WA。4.2 lower_bound 和 upper_bound 选反严格上升子序列用 lower_bound找第一个大于等于 x 的位置。如果你要求非降序也就是允许 a[j] a[i] 延续子序列要改成 upper_bound。我以前写题时就用反过一次数据强一点直接WA。怎么自测构造样例 [2, 2, 3]如果是求严格LIS答案长度2对应 [2,3]用 lower_bound 会得到2。如果错误地用 upper_bound第一个大于2的位置是下标2元素3替换后 d[2,2,3]等等这里我重新推一下读到第一个2d[2]读到第二个2upper_bound 找到第一个大于2的位置也就是末尾 end于是 pushd[2,2]读到3也 pushd[2,2,3]长度3。和正确结果2就不一致了。用 [2,2,2] 更明显正确严格LIS长度1lower_bound 得到 d[2]长度1upper_bound 会不断追加得到 d[2,2,2]长度3结果就错了。所以拿全相同元素的样例验证很快。4.3 重复元素到底怎么处理原题如果保证是1到n的排列就不存在重复问题。但我见过不少变体序列里的正整数可能重复。如果目标序列只要非降序LIS就按非降序求d数组里允许相等元素不断 push也就是用 upper_bound 替换。如果目标要求严格递增那重复的 x 不可能同时出现在最终序列里这种情况下直接用 lower_bound 求严格LIS即可输出答案时多出来的重复元素也要当作需要移动的元素语义上没有问题。不过要注意如果重复值很多答案会很大别把 d.size() 和值域搞混。d.size() 只表示最长上升子序列的长度和值域完全没有关系。4.4 调试技巧与暴力对拍这种思维量不小的题我强烈建议写一个暴力程序对拍。暴力程序思路很直接n很小的时候枚举所有可能的移动结果或者用BFS搜最少步数然后和 O(n log n) 算法输出对比。但枚举移动路径写起来也不容易更简单的对拍思路是写一个直接暴力生成所有子序列找LIS的小函数n 20与 nlogn 算法结果对比。下面是我习惯在本地用的对拍框架// brute: O(2^n) 枚举子序列是否保留 int bruteLIS(const vectorint a) { int n (int)a.size(), best 0; for (int mask 0; mask (1 n); mask) { int pre 0, len 0; bool ok true; for (int i 0; i n; i) if (mask i 1) { if (a[i] pre) { ok false; break; } pre a[i]; len; } if (ok) best max(best, len); } return best; }主程序里用随机数据对比 fastLIS 的结果。对拍数据可以设计几种升序、降序、全相同、随机小范围、随机大范围。能过这五类正确性基本稳了。4.5 n很小或已经有序等边界情况n1时LIS长度就是1答案0代码自然成立。已经有序的数组d 在扫描中不断 pushLIS长度n输出0。完全逆序排列LIS长度1输出 n-1。边界情况一般不会出问题但要在考试时留出两分钟自测这三组样例能有效防止低级失误。提示输出类型记得用 intn 最大1e6时答案也在 int 范围内但如果 n 开到1e7就要考虑用 long long。虽然题目一般不会到这个量级我仍习惯把减法结果用 long long 输出没有任何坏处。5. 同类变体与思路迁移5.1 交换相邻元素的最小操作逆序对同样是“把序列变有序”操作从移动到任意位置变成只能交换相邻两个位置问题就变成了求逆序对数量。这是因为每次交换相邻元素恰好能让一对逆序关系颠倒最小交换次数等于逆序对数。归并排序或者树状数组都可以在 O(n log n) 内解决。这个模型和 n-LIS 的区别经常被拿来对比。同样一个序列 [3, 1, 2]n-LIS 模型答案是 3-21因为保留 [1,2]把3插到最前面即可而相邻交换模型答案是2因为 3 要跨过 1 和 2 两个元素才能到最前面。理解了操作力度不同答案不同就顺理成章了。5.2 任意交换两个元素置换环如果每次操作是交换任意两个位置上的元素不是移动插入答案又不一样。对于1到n的排列最少交换次数是 n 减去置换环的个数。比如 [3, 1, 2]置换环是 (1,3,2)一个环n3答案是2。这个模型考察的是排列的循环分解和LIS完全不是一条路子。我做题时最怕的就是这三种模型互相混淆所以现在看序列操作题第一件事就是圈出“操作动词”移动、交换相邻、任意交换三个词三套解法。把这个对照表记熟练后再遇到类似描述的题就不会慌。5.3 带额外约束的变体还有一些变体会加限制比如只能把元素移动到序列开头问最少移动几次。这种问题可以从后往前扫维护当前期望的末尾值能贪心就贪心解法和 n-LIS 也不完全一样。再比如带权移动、分成若干段要求段内有序等就需要结合线段树、树状数组做更复杂的DP。不过万变不离其宗大多数序列重构问题的核心还是确定哪些元素可以保留在原位剩下的元素用一次操作各归其位。把握住“不动子序列”这条主线审题就不容易歪。这也是我在刷完一本通高手训练这一章的序列题之后回头看这道1680时最深的感受。最后分享一点个人体会。我最早接触这道题时第一反应是去模拟小a的各种移动方案试图找出贪心策略结果被数据范围劝退。后来才意识到这类题真正考的是“逆向思维”不是选择移动谁而是选择不移动谁。只要把“不动的骨架”想清楚答案就是 n 减去最长上升子序列的长度代码十个if都不到。对拍和边界测试在我自己训练中帮了大忙尤其是 lower_bound 和 upper_bound 的区别建议你写题时也专门准备一个全相同元素的小样例来验证。如果后面遇到移动、交换、插入混在一起的变体多回来看看上面那张模型对比表应该会很有用。