1. 从友好城市这个标题说起它到底在考什么第一次看到友好城市这个题目名很多人会以为是图论或者并查集毕竟城市两个字太容易让人联想到连通性、最短路这些经典模型。但真正把题目读完就会发现它其实是一道非常典型的最长上升子序列LIS变形题只不过套了一层配对的外衣。题目的核心场景是这样的河的两岸各有若干个城市北岸城市和南岸城市之间存在若干条友好关系航线。现在要在这条河上修桥要求任意两座桥不能交叉。问最多能修多少座桥。这个不能交叉的约束就是整道题的灵魂。它把一个看起来像二分图匹配的问题硬生生转化成了一个一维的序列问题。为什么因为一旦你按某一岸的城市坐标排序另一岸对应的坐标就必须满足单调性否则两座桥必然交叉。我见过太多人在这道题上卡住不是因为不会写LIS而是因为没想通排序这一步为什么能成立。他们要么直接上二分图匈牙利算法要么试图用区间DP去枚举结果要么超时要么状态设计错误。其实这道题一旦想通转化逻辑代码量不到三十行。这篇文章我会从为什么排序能消除交叉约束讲起把转化过程拆到每一步都能自己复现然后给出LIS的两种写法朴素O(n²)和二分O(n log n)再补充几个实际写代码时容易踩的坑比如坐标重复、排序方向、边界初始化。适合正在刷算法题、想搞懂LIS类变形题的读者也适合已经会写LIS但一遇到应用题就懵的人。2. 为什么桥不能交叉等价于序列单调2.1 用几何直觉理解交叉条件先把场景画在脑子里一条河横在中间北岸是一条直线南岸是另一条平行直线。北岸城市用坐标 x₁ 表示南岸城市用坐标 x₂ 表示。一座桥连接北岸的 a 和南岸的 b在图上就是一条线段。现在考虑两座桥桥1连接 (a₁, b₁)桥2连接 (a₂, b₂)。假设在北岸方向上 a₁ a₂。如果这两座桥不交叉那么在南岸方向上必须也有 b₁ b₂。反过来如果 b₁ b₂那么从 a₁ 出发的线要连到更靠右的 b₁从 a₂ 出发的线要连到更靠左的 b₂两条线段必然在河面上相交。这个结论可以用初中的几何知识验证两条线段如果端点分别在两条平行线上且端点顺序相反那么它们一定相交。这不是概率问题是必然的。所以所有桥互不交叉这个约束翻译成数学语言就是如果按北岸坐标从小到大排序那么对应的南岸坐标必须严格递增。2.2 排序是消除交叉约束的关键操作很多人会问为什么一定要排序不排序行不行不排序的话你面对的是一个二维的配对选择问题从若干对 (a, b) 中选出最多的对使得不存在 i, j 满足 aᵢ aⱼ 且 bᵢ bⱼ。这是一个典型的二维偏序问题直接做需要树状数组或者CDQ分治。但如果我们先按北岸坐标排序那么 a 这一维就自动有序了。此时只需要保证 b 递增就等价于原约束。问题从二维降到了一维这就是排序的价值。注意排序之后我们实际上是在北岸有序的前提下做选择。因为桥的修建不要求覆盖所有城市只要求选出的桥互不交叉所以排序不会丢失任何可行解——任何一组互不交叉的桥按北岸坐标排序后南岸坐标必然也是递增的。2.3 从配对到序列问题转化的完整链路把转化过程完整写一遍读入所有友好关系对 (a, b)表示北岸城市 a 和南岸城市 b 可以修桥。按 a 从小到大排序。如果 a 相同按 b 从小到大排序这一点后面会详细讲为什么。取出排序后的 b 序列。问题变成在这个 b 序列中最多能选出多少个元素使得它们严格递增。这就是最长上升子序列问题。整个转化的核心在于第2步和第4步。第2步把二维约束压成一维第4步把选桥变成选递增子序列。想通这两步剩下的就是LIS模板。3. 最长上升子序列的两种写法与选择依据3.1 朴素DPO(n²)的写法与适用场景LIS最直观的写法是动态规划。定义 dp[i] 表示以第 i 个元素结尾的最长上升子序列长度。转移方程dp[i] max(dp[j]) 1, 其中 j i 且 b[j] b[i]初始时每个 dp[i] 1因为至少可以选自己。代码实现def lis_n2(arr): n len(arr) if n 0: return 0 dp [1] * n for i in range(n): for j in range(i): if arr[j] arr[i]: dp[i] max(dp[i], dp[j] 1) return max(dp)这个写法的时间复杂度是 O(n²)空间 O(n)。当 n 在几千以内时完全够用。它的优点是逻辑直白不容易写错而且方便记录具体选了哪些元素如果需要输出方案的话。我一般建议如果题目数据范围 n ≤ 5000直接用这个写法省事。AcWing上这道题的数据范围通常在几千O(n²)能过。3.2 二分贪心O(n log n)的优化思路如果 n 到了十万级别O(n²)就危险了。这时候需要用二分优化。核心思想是维护一个数组 tails其中 tails[k] 表示长度为 k1 的上升子序列的末尾元素的最小值。这个数组有一个重要性质它一定是严格递增的。为什么假设 tails[k] ≥ tails[k1]那么长度为 k2 的上升子序列的倒数第二个元素一定小于 tails[k1]也就小于 tails[k]那长度为 k1 的子序列末尾可以更小矛盾。基于这个性质对于每个新元素 x我们可以在 tails 中二分找到第一个大于等于 x 的位置替换它。如果 x 比所有元素都大就追加到末尾。import bisect def lis_nlogn(arr): tails [] for x in arr: pos bisect.bisect_left(tails, x) if pos len(tails): tails.append(x) else: tails[pos] x return len(tails)这里用 bisect_left 而不是 bisect_right是因为我们要求严格递增。如果允许非严格递增即可以相等就要用 bisect_right。提示tails 数组本身并不是某个具体的上升子序列它只是记录了每个长度对应的最小末尾值。最终 tails 的长度就是LIS的长度但 tails 里的元素不一定构成原序列中的合法子序列。这一点经常有人搞混。3.3 两种写法的对比与选型建议维度O(n²) DPO(n log n) 二分时间复杂度O(n²)O(n log n)空间复杂度O(n)O(n)代码复杂度低中能否输出方案容易需要额外记录适用数据范围n ≤ 5000n ≤ 10⁵ 或更大严格递增支持是用 bisect_left非严格递增支持改条件即可用 bisect_right我的建议是平时刷题两种都写一遍理解它们的等价性。比赛时看数据范围选。如果时间紧直接背二分版本因为它适用范围更广。4. 排序细节相同坐标到底怎么处理4.1 北岸坐标相同时的排序方向这是这道题最容易出错的地方之一。假设有两对关系(a1, b5) 和 (a1, b3)。北岸坐标相同都是1。这两座桥能同时修吗从几何上看两座桥都从北岸的同一个点出发连到南岸的不同点。它们只在北岸端点重合在河面上并不交叉除非认为共端点算交叉。但题目通常要求桥不能交叉共端点是否允许取决于题意。在AcWing 1012这道题中通常认为同一个北岸城市只能修一座桥因为一个城市修两座桥到两个不同城市这两座桥共享端点在实际场景中不太合理。但题目输入可能不会出现重复的北岸坐标或者即使出现我们也可以通过排序策略来处理。关键点如果按 a 升序a 相同时按 b 升序那么在 b 序列中相同 a 对应的 b 是递增的。此时如果LIS允许严格递增这些 b 可以同时被选中意味着同一个北岸城市修了多座桥。如果题目不允许就需要在排序时让 a 相同时 b 降序这样在LIS中它们不可能同时被选因为后面的 b 更小不满足递增。4.2 南岸坐标重复的影响如果两个不同的北岸城市 a₁ a₂但对应的 b 相同即 b₁ b₂。这两座桥能同时修吗从几何上看两座桥从不同北岸点出发连到南岸同一个点。它们在南岸端点重合。同样是否允许取决于题意。如果要求严格不交叉且不共端点那么 b 必须严格递增相等的 b 不能同时选。此时LIS用严格递增即可。如果允许共端点那么 b 可以非严格递增LIS用非严格递增。注意AcWing 1012的标准题意是桥不能交叉通常理解为不能有公共点包括端点所以用严格递增。但实际写题时要看清题目描述。如果题目说任意两座桥不能相交一般包含端点相交。4.3 一个具体的排序去重案例假设输入关系为(1,3), (1,5), (2,4), (2,6), (3,5)。按 a 升序a 相同按 b 升序排序后b序列为 [3,5,4,6,5]。如果直接用严格递增LIS结果是 [3,4,6] 或 [3,4,5]长度为3。这意味着选了 (1,3), (2,4), (3,5) 或 (1,3), (2,4), (2,6)等等(2,4)和(2,6)的a相同不能同时选。但LIS选的是b序列中的元素b4和b6对应的是a2的两个不同关系。如果LIS同时选了它们就表示北岸城市2修了两座桥这通常是不允许的。所以如果题目限制一个城市只能修一座桥我们需要在排序时对相同a的处理做文章。具体做法按a升序a相同时按b降序。这样b序列变成 [5,3,6,4,5]。此时LIS严格递增的结果是 [3,4,5] 或 [3,4,6]实际上[5,3,6,4,5]的严格递增LIS是[3,4,5]或[3,4,6]让我算一下3,4,5是递增的对应(1,5)?不对3对应(1,5)排序后是(1,5),(1,3),(2,6),(2,4),(3,5)b序列[5,3,6,4,5]。LIS可以是[3,4,5]对应(1,3),(2,4),(3,5)a分别是1,2,3没有重复正确。所以关键结论如果题目要求每个城市最多修一座桥排序时a相同按b降序如果允许一个城市修多座桥只要不交叉按b升序。AcWing 1012的输入通常保证北岸城市坐标互不相同或者题意默认一个城市只修一座桥。保险起见我建议按a升序、a相同按b降序来排序这样LIS严格递增就能自动保证每个a只选一次。5. 完整代码实现与逐行注释5.1 Python版本从读入到输出import sys import bisect def main(): data sys.stdin.read().split() if not data: return n int(data[0]) pairs [] idx 1 for _ in range(n): a int(data[idx]) b int(data[idx1]) idx 2 pairs.append((a, b)) # 按北岸坐标升序相同则按南岸坐标降序 pairs.sort(keylambda x: (x[0], -x[1])) # 提取南岸坐标序列 b_seq [p[1] for p in pairs] # 二分法求严格递增LIS tails [] for x in b_seq: pos bisect.bisect_left(tails, x) if pos len(tails): tails.append(x) else: tails[pos] x print(len(tails)) if __name__ __main__: main()这段代码的输入格式假设是第一行一个整数n接下来n行每行两个整数a和b。如果实际输入格式不同需要调整读入部分。5.2 C版本适合竞赛环境#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorpairint,int pairs(n); for (int i 0; i n; i) { cin pairs[i].first pairs[i].second; } sort(pairs.begin(), pairs.end(), [](const pairint,int x, const pairint,int y) { if (x.first ! y.first) return x.first y.first; return x.second y.second; }); vectorint tails; for (auto p : pairs) { int x p.second; auto it lower_bound(tails.begin(), tails.end(), x); if (it tails.end()) { tails.push_back(x); } else { *it x; } } cout tails.size() endl; return 0; }C的 lower_bound 默认是找第一个大于等于x的位置正好对应严格递增LIS。如果要用非严格递增改成 upper_bound。5.3 边界情况与初始化检查几个必须检查的边界n 0没有友好关系输出0。代码中tails为空输出0正确。n 1只有一对关系输出1。tails会有一个元素正确。所有b相同比如b序列[3,3,3]严格递增LIS长度为1。bisect_left每次都会替换第一个位置tails长度保持1正确。b序列已经严格递增比如[1,2,3,4]每次x都大于tails末尾直接append长度4正确。b序列严格递减比如[4,3,2,1]每次x都替换tails[0]长度1正确。提示如果题目要求输出具体选了哪些桥需要在DP版本中记录前驱二分版本则需要额外维护一个数组记录每个元素在LIS中的位置。但AcWing 1012只要求输出最大数量所以不需要。6. 实际写题时踩过的坑与排查思路6.1 排序方向写反导致答案偏小我第一次写这道题时按a升序、a相同按b升序排序结果在某些测试数据上答案比预期小。排查了半天才发现当a相同时b升序会让LIS可能同时选中同一个a的多个b但题目不允许一个城市修多座桥。改成b降序后同一个a的b在序列中递减LIS严格递增就不可能同时选中它们。这个坑的排查方法构造一组有重复a的数据手动模拟LIS过程看是否会选中同一个a的多个b。如果会就说明排序方向需要调整。6.2 严格递增与非严格递增混用另一个常见错误是LIS的严格性搞错。如果题目允许桥共端点那么b可以相等此时应该用非严格递增LISbisect_right。如果题目不允许共端点用严格递增bisect_left。我建议先按严格递增写如果答案偏小再考虑是否题目允许共端点。但AcWing 1012的标准题意是严格不交叉所以严格递增是对的。6.3 输入格式与多组数据的处理有些平台的输入可能包含多组测试数据或者n和关系对在同一行。这时候用 sys.stdin.read().split() 一次性读入所有token是最稳妥的避免逐行读取时格式不一致的问题。如果题目明确只有一组数据也可以逐行读。但竞赛中我习惯用read().split()省心。6.4 数据范围导致的超时问题如果n到了10⁵O(n²)的DP会超时。这时候必须用二分版本。我一般直接写二分版本因为它的代码量也不大而且不用担心数据范围。如果n到了10⁶二分版本的O(n log n)也可能吃力但一般算法题不会给这么大。真到了这个级别需要考虑更高级的数据结构或者题目本身有特殊性质。7. 从这道题延伸出去的同类问题7.1 最长不下降子序列的变体把严格递增改成非严格递增就是最长不下降子序列。处理方法很简单二分时用 upper_bound 代替 lower_bound。在排序时如果a相同按b升序配合非严格递增LIS也能处理某些允许共端点的场景。7.2 二维偏序与导弹拦截问题友好城市本质上是二维偏序的一个特例。更一般的二维偏序问题是给定若干点 (x, y)求最多能选出多少个点使得x和y都递增。如果x已经有序就退化成LIS。如果x无序就需要先排序再LIS或者用树状数组。经典的导弹拦截问题也是LIS的变形第一问求最长不上升子序列第二问求最少的不上升子序列覆盖数后者等价于最长上升子序列长度Dilworth定理。7.3 排序LIS的通用解题框架遇到选最多元素满足某种单调性的问题可以套这个框架确定哪个维度可以排序排序后该维度自动满足约束。把另一个维度提取成序列。根据约束的严格性选择LIS的严格/非严格版本。注意相同第一维时的排序方向避免选中不允许的组合。这个框架能解决一大类问题包括区间调度、信封嵌套、俄罗斯套娃等。7.4 与二分图匹配的区别有人会想这不是二分图最大匹配吗北岸城市和南岸城市配对要求边不交叉。但二分图匹配求的是最大匹配数不考虑边的几何交叉。如果加上不交叉约束就不能直接用匈牙利算法因为匹配算法不知道几何信息。实际上不交叉约束把问题从一般的二分图匹配降到了LIS这是约束带来的福利。如果没有这个约束问题会难得多。8. 我个人在这道题上的经验总结刷这道题最大的收获不是学会了LIS而是理解了排序如何消除维度约束。很多算法题看起来复杂其实就差一个排序。排序之后原本需要二维数据结构的问题变成了一维原本需要复杂状态设计的问题变成了模板题。另一个体会是不要急着写代码先把转化逻辑想清楚。我见过太多人一看到城市就往上套图论结果绕了一大圈才发现是LIS。花五分钟想清楚问题的本质比花半小时调试错误代码划算得多。最后说一个实用技巧写完LIS后用几组小数据手动验证。比如n3关系为(1,3),(2,2),(3,1)排序后b序列[3,2,1]LIS长度为1意味着最多修一座桥。这符合直觉三座桥的b递减任意两座都会交叉。再比如(1,1),(2,2),(3,3)b序列[1,2,3]LIS长度为3三座桥都不交叉。用这种极端数据验证能快速发现排序或LIS写法的错误。如果后续想扩展可以尝试输出具体的建桥方案或者处理带权重的版本每座桥有收益求最大收益。带权版本就不能直接用LIS了需要变成最大权上升子序列用树状数组优化DP。那是另一个话题了。
