1. 题目到底在讲什么UVa 13276 这道题题面借了动画电影《Megamind》的名义讲的是大反派面前有一串编号从 1 到 N 的卡片初始顺序完全乱掉了。他每次可以挑出任意一张卡片把它插回任意位置包括开头和结尾。目标是用最少的操作次数把这串卡片排成严格递增的序列排序。仔细想想这个操作有多“霸道”普通排序题里你通常只能交换相邻元素或者像插入排序一样把某个元素往前挪一位但这里允许你一次性把任意元素直接扔到任意位置相当于一次操作就能跨越任意多个元素。这样强力的操作下最少到底需要几步我第一次看到这题直觉是“模拟一下每次把当前最小的没放对位置的元素拿出来放到前面”。这个思路听上去合理但很快就被反例打脸了。举个很简单的例子序列[3, 1, 2]。如果照贪心的思路先把最小的 1 挪到开头得到[1, 3, 2]然后还得挪 2总共两次。但如果你直接把 3 挪到最后一次操作就得到[1, 2, 3]。所以贪心根本不管用问题一下变得有意思了。本题的数据范围我记得 N 可以到 100000 左右这意味着 O(N^2) 的解法在大数据下必挂必须想一个更聪明的数学结构。很多人拿到这题会试着直接构造操作方案这其实走偏了。正确的方向是先想清楚在最终排好的序列里有哪些元素是可以“完全不动”的动得越少总操作次数就越少而“不动”的元素必然已经满足某种顺序条件。这样问题就从“怎么移动”变成了“找最长的合法不动子序列”一下子转到我们熟悉的动态规划领域了。2. 从“移动元素”到“最长上升子序列”核心转换我们先认真分析一下“不动”这个词的精确含义。假设最终序列是[1, 2, 3, ..., N]。如果你从头到尾都没有碰过某几个元素那它们在原始序列里的相对位置关系就必须和最终顺序一致。什么意思如果数值小的元素原本在数值大的元素后面你又不移动它们那排序完成后它们还是这个顺序肯定不正确。所以所有不动的元素按它们在原始序列出现的位置来看数值必须是严格递增的。这就是最长上升子序列LIS的定义在一个序列中找一个长度最长的子序列使得子序列中元素的数值严格递增同时它们在原序列中的位置也是递增的。举个例子原序列[1, 3, 2, 4]它的 LIS 可以是[1, 3, 4]也可以是[1, 2, 4]长度都是 3。那答案是不是就是N - LIS长度 4 - 3 1验证一下把 3 和 2 中的 2 挪到 3 前面得到[1, 2, 3, 4]确实一次操作就够了。这里有一个特别容易让人绕进去的误区很多初学者会以为留下的元素数值必须连续比如只能留[2, 3, 4]这样连号的片段。我一开始也这么以为后来发现完全错误。看一个例子[1, 2, 4, 3]LIS 是[1, 2, 4]三个元素分别是 1、2、4中间缺了个 3。按照我们的公式答案应该是 1。实际操作也很简单把 3 从末尾拿出来插到 2 和 4 之间就变成了[1, 2, 3, 4]。注意留下来的 1、2、4 一次都没动过而缺的那个 3 是靠一次移动补上的。所以你不需要留下“数值连续”的子序列只需要留下一个普通的上升子序列剩下的缺口全部靠移动来填。这个认知如果不纠正后面的推导全都是歪的。再说得直白一点你留下的元素相当于一个“骨架”它们本来就已经排对了相对顺序。其他元素就像积木一样被抽出来往骨架的缝隙里插。骨架越长需要插的积木就越少。所以“尽可能让骨架长”就是我们要做的事而“最长骨架”就是 LIS。3. 严格证明N - LIS 就是答案光有直觉还不够我们得验证两个方向能不能做到 N - LIS 次以及是不是至少需要这么多。首先证明“上界”也就是存在一种方案只用 N - LIS 次操作就完成排序。假设我们已经找到了一个长度为 L 的 LIS把它作为稳定框架。剩下 N - L 个元素我们从左到右依次处理。每次取出一个不属于 LIS 的元素直接插到它最终该在的位置。因为 LIS 内部的相对顺序本来就是正确的插入其他元素不会干扰它们的相对位置所以这个操作过程是安全且可复现的。每处理一个元素只花一次操作总共就是 N - L 次。这个构造方法非常直观代码里甚至不需要真的去模拟因为你只是需要证明解的存在性。然后证明“下界”也就是没有任何方案能用少于 N - L 次完成排序。假如你总共只做了 k 次操作那么就至少有 N - k 个元素从头到尾没动过。没动过的元素必须构成一个严格上升子序列否则最终序列不可能是递增的。所以没动过的元素数量最多不超过最长上升子序列长度 L也就是说 N - k ≤ L。把不等式调一下得到 k ≥ N - L。这就证明了任何方案都至少需要 N - L 次操作。上界和下界碰到一起答案就锤死了最小值恰好等于 N 减去 LIS 长度。这个证明的优雅之处在于它压根不用关心你具体怎么移动那些非 LIS 元素只需要抓住“没动过的东西必须有序”这个铁律。做题时只要把证明链条写清楚哪怕代码写挂了思路方向也不会错。再额外验证几个刁钻的例子。[2, 1, 3, 4]的 LIS 是[1, 3, 4]或[2, 3, 4]长度 3答案为 1移动 2 到开头即完成。[4, 3, 2, 1]的 LIS 长度是 1任意单个元素答案为 3事实也的确如此你得把三个元素依次挪到正确位置才行。[1, 2, 3, 4]已经有序LIS 就是整个序列长度为 4答案为 0什么都不用做。这些例子都能对上。4. 高效计算 LIS二分查找法现在问题的焦点变成了给定一个长度为 N 的排列怎么快速求出它的 LIS 长度N 如果只有几百可以直接交给 O(N^2) 的动态规划定义dp[i]为以第 i 个元素结尾的 LIS 长度转移时扫一遍前面所有元素看能不能接到后面。这个写法简单但慢在大数据下必然 TLE。4.1 贪心 二分为什么能成立于是搬出经典 O(N log N) 做法。核心是一个辅助数组dd[k]表示“当前已经处理的元素中长度为 k 的上升子序列的最小末尾值”。为什么只保留最小末尾值就够因为对于同样长度的子序列末尾越小后面接到更大数字的可能性就越大。这个道理跟买股票类似同样的仓位成本越低越好。d数组一定严格递增这一点可以严格归纳证明。遍历原序列的每一个数x在d里用二分查找找到第一个大于等于x的位置p。如果p不存在即x比d里所有数都大说明x可以接在最长的子序列后面形成一个新的更长子序列于是把x追加到d末尾。否则用x替换d[p]表示我们找到了一个末尾更小、同样长度的上升子序列。最后d的长度就是 LIS 长度。这里有一点要注意题目给的序列是排列没有重复数字所以严格上升子序列和直接找“第一个大于等于”的位置是等价的。如果你以后在其他题目里碰到允许重复的情况求“非降子序列”就需要改用upper_bound否则会把相等的元素误当成可以“覆盖”的对象导致长度算不准。这是我踩过的真实坑后面专门写一节提醒大家。4.2 代码实现C我平时刷 UVa 习惯用 C模板如下#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; while (cin N) { vectorint d; for (int i 0; i N; i) { int x; cin x; 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; }注意几点ios::sync_with_stdio(false)和cin.tie(nullptr)可以加速输入输出建议加上UVa 上的输入量有时候不小。lower_bound返回的是第一个不小于x的迭代器正好对应“第一个大于等于”的位置。最终答案直接输出N - d.size()注意把size_t转成int否则运算符优先级可能给你带来麻烦虽然这里只是减号但养成习惯总没错。4.3 Python 版本如果你更习惯 Python用bisect模块一行就能搞定查找import bisect import sys def solve(): data sys.stdin.read().split() idx 0 out_lines [] while idx len(data): n int(data[idx]); idx 1 d [] for _ in range(n): x int(data[idx]); idx 1 pos bisect.bisect_left(d, x) if pos len(d): d.append(x) else: d[pos] x out_lines.append(str(n - len(d))) sys.stdout.write(\n.join(out_lines)) if __name__ __main__: solve()bisect.bisect_left对应 C 的lower_bound。Python 的列表插入尾部平均 O(1)二分查找 O(log N)整体依然是 O(N log N)。要注意 UVa 的老版本 Python 可能只支持 2.7如果在线提交平台比较旧记得把语法调回 Python 2 兼容模式。我自己在本地测试用 Python 3 没问题但如果要提交到老平台最好用 C省得版本兼容问题让人血压升高。5. 复杂度分析与边界条件这个算法的时间复杂度是 O(N log N)其中 N 是序列长度。空间复杂度 O(N)。对于 UVa 13276 这种带有多个测试用例的题目每组用例都要重新初始化d可不能把上一轮的数组残留带到下一轮否则答案直接飞掉。边界条件上题目一般保证 N 是正整数但严谨起见也可以考虑 N 0 的情况。当 N 为 0 时d为空LIS 长度为 0输出 0 - 0 0逻辑上是自洽的。不过实际提交中很少出现空数据所以不用过度担心。另一个边界是输入格式。UVa 的老题目常常是“一个整数 N 占一行下一行 N 个整数”但也可能 N 和后面的数字混在几行里。我最推荐的写法是持续读入碰到整数就处理用cin或read().split()都能应对跨行情况。如果你用scanf但读错格式非常容易出现莫名 WA。我早期在 UVa 上栽过几次都是因为假定“一行一个数字”结果数据实际跨行把后面的数字当成下一组的 N 来读了。还有一个小地方如果题目说 N 可能特别大比如 10 万甚至 100 万递归写 LIS DP 会栈溢出但二分法用循环完全没有这个问题。所以这个解法在性能层面非常稳。6. 我在实战中踩过的坑我现在把这些坑一个个写出来每个都是我真实犯过的错误希望能帮读者少走弯路。第一个坑把“上升子序列”理解成“值连续的子序列”。这个我之前反复强调了但具体到代码里它还会以另一种方式坑你。比如你写出来的程序去找“相邻数值差为 1 的最长链”样本一过可能对样本二就错。我当时做了一个测试[1, 2, 4, 3]正确答案是 1而错误算法得出 2保留[1,2,4]或[1,2,3]长度都是 3等等这里好好算一下。其实你会发现只要找普通 LIS答案立刻正确。所以一旦出现反例第一反应就是检查模型是不是过度约束了。第二个坑二分包边界搞混淆。求严格上升子序列应该用lower_bound第一个 x 的位置求非降子序列应该用upper_bound第一个 x 的位置。原题是排列没有重复值所以两者表面上没区别但我后来在另一道允许重复的题里惯性使用了lower_bound结果算出的长度明显偏大。教训是不要因为当前题目没有重复就忽略语义你在总结模板时应该把两种写法都记清楚。第三个坑多组数据之间的变量残留。有一次我忘了清空d直接把下一组数据继续往原数组里塞导致答案越来越大WA 得莫名其妙。其实处理方式很简单每次循环开头都新建一个局部vectorint d或者手动d.clear()。在 C 里局部变量会自动销毁所以我后来习惯把每组数据的处理逻辑放进一个函数里。第四个坑输出格式多空行。UVa 的评测器对空白字符相当敏感如果你在每组输出后面多打一个空行可能被判 Presentation Error。最稳妥的方式是像我在 Python 代码里那样把所有答案存进一个列表最后用join输出保证每行一个答案末尾不多一个换行。C 就简单cout ans \n即可。第五个坑只看题面不看输入规模。有些 UVa 老题没有明确给 N 的范围我从样例推测 N 很小于是用了 O(N^2) 的 DP提交后 TLE。后来才意识到数据量远超预想。建议做题前先看讨论区或者题目标签搞清楚约束再决定算法。7. 延伸一类“移动元素排序”问题的通用解法UVa 13276 这类题最大的价值是训练我们识别“任意位置移动”这种操作的数学本质。以后只要见到“你可以随意把元素移到任意位置”的排序题第一反应就应该往 LIS 上靠。举例说如果操作限制成“只能把任意元素移到序列开头”那问题就变成求“最长后缀满足递增且连续”之类的结构解法完全不同。如果操作限制成“只能交换相邻两个元素”那就是经典逆序对数。如果操作允许“任意交换两个元素”那答案就是 N - 置换中的循环数。这些变体之间差别很大但它们都指向同一个分析框架先把“不可移动的骨架”是什么定义清楚然后看剩下的部分怎么补。我还特别喜欢把这题和 Codeforces 上一些类似的LIS题联系起来刷。比如有一类题问“最少需要移动多少个元素使得数组有序”它们其实就是这道题的换皮版本。只要把一个数列的 LIS 求出来答案“嗖”地就出来了。真正吃过亏之后你会发现很多“看似贪心”的题目背后藏的都是经典序列算法。我自己刷完这题后特意整理过一个笔记记录了三种“移动排序”题型的对比表格这里分享给你操作方式等价核心问题时间复杂度移动任意元素到任意位置N - LIS 长度O(N log N)移动任意元素到序列开头N - 最长后缀连续递增长度O(N)交换相邻元素逆序对数O(N log N)任意交换两个元素N - 循环数O(N)这张表我强烈建议收藏。做题时先看清操作定义然后直接对照表格找模型能省下大量试错时间。最后再分享一个做题小技巧任何算法题在你写代码之前先在草稿纸上画一组长度为 4 或 5 的排列手动推一遍答案再拿你的算法去跑。比如[2, 4, 1, 3]LIS 是[2, 4]或[1, 3]长度 2答案是 2。你手动试一下是不是真的两步能完成把 1 挪到最前面得到[1, 2, 4, 3]再把 3 挪到 4 前面得到[1, 2, 3, 4]确实两步。这种小样例不仅帮助你验证公式还会让记忆更深刻。UVa 13276 Megamind 这道题看起来是模拟题实际上是标准的 LIS 题。刷完它你对“移动排序”这一类问题的理解会上升一个层次。下次再遇到类似的题目你就能迅速看穿背景设定直接拆出核心算法模型。我个人觉得这才是刷 OJ 最大的乐趣所在。