形式化题目

河的两岸各有若干城市，给出 $n$ 对友好城市 $(x_i, y_i)$：$x_i$ 是南岸坐标，$y_i$ 是北岸坐标。每对城市申请修建一条连接两岸的直线航道 $l_i$。

要求从这 $n$ 对中选出尽可能多的对，使得任意两条被选中的航道都不在河面上交叉，输出最多能批准的对数。

把每对看成平面上的点 $(x_i, y_i)$ 后，题目的核心结构是：两条航道 $l_1 = (x_1,y_1)$、$l_2 = (x_2,y_2)$ 内部相交，当且仅当

即一个点的横坐标更小而纵坐标更大（或反之）。坐标相等时两条航道共端点或平行，不算交叉。

样例中共有 7 对申请。按南岸坐标排好序后，把两岸的坐标各画成一排，一对城市之间连一条线：

1
2
3
4南岸 x:   2    4    9   10   15   17   22
          │    │    │    │    │    │    │
北岸 y:   6    2    8    3   12   17    4
选中  :   ✓         ✓         ✓    ✓

观察重点是：排序后 $x$ 从左到右递增，于是两条航道是否相交只由 $y$ 决定。例如最左边两对 $(2,6)$ 和 $(4,2)$，左边的 $y$ 更大，两条线必然交成一个叉；而打 ✓ 的 4 对 $(2,6),(9,8),(15,12),(17,17)$ 的 $y$ 值 $6,8,12,17$ 依次不下降，两两都不交叉，正好给出样例输出的 4。

正解

思路

第一步：把几何条件翻译成一维顺序。 两条航道是否相交，只取决于两个端点的相对顺序。把所有申请按南岸坐标 $x$ 升序排好之后，$x$ 这一维就固定了"谁在左、谁在右"，剩下的约束全部落在北岸坐标 $y$ 上：

• 左边那条的 $y$ 更小：两条线是"左下 → 右上"的平行走向，不相交；
• 左边那条的 $y$ 更大：两条线一条向右上、一条向右下，必然相交。

于是"航道两两不交叉"就等价于：按南岸排序后，被选中的点其北岸坐标单调不下降。

排序时还要处理南岸坐标相同的情况：两对城市的南岸是同一个点，两条航道只在这个岸上端点处相接，不算交叉，所以它们可以同时被选中。把排序键写成整个元组 (x, y)（即 $x$ 相同时再按 $y$ 升序），就能保证这些点自然按 $y$ 递增排列，不会因为输入顺序而被错误地拆开。

第二步：识别模型。 排序只是预处理，真正的任务是：从北岸坐标序列 $y_1, y_2, \dots, y_n$（此时 $x$ 已升序）中选出尽量多的元素，使它们保持原相对顺序且单调不下降，即最长不下降子序列（LNDS）。

第三步：为什么是"不下降"而不是"严格上升"。 题面声称两岸坐标互不相同，但真实数据中确实出现了重复坐标；而 $y$ 相等、$x$ 不同的两条航道只是平行，并不相交，所以相等的 $y$ 必须允许连续取。这一点在实现里体现为二分时取右侧插入点。

第四步：优化 DP。 最朴素的 LNDS 是 $O(n^2)$：

瓶颈在"前面所有满足 $y_j \leqslant y_i$ 的最大 $dp[j]$"这次查询。注意到一个单调性：子序列越长，它可用的最小结尾值就越大。于是维护数组 tails，规定

tails[k] = 目前所有长度为 $k+1$ 的不下降子序列中，最小的结尾值。

这个数组关于下标 $k$ 单调不降（长度更长，结尾不可能更小），所以对一个新的 $y_i$ 可以直接二分：

• pos = bisect_right(tails, y_i) 找到第一个大于 $y_i$ 的位置；
• 若 pos == len(tails)，说明 $y_i$ 能接在当前最长链后面，链长加一；
• 否则把 tails[pos] 覆盖成 $y_i$：同样能得到长度 pos+1 的链，但结尾更小，只会给后面留出更多空间，不会丢掉任何可能。

用样例走一遍，排序后的北岸序列是 $6,2,8,3,12,17,4$：

最后一行的 tails 是 $[2,3,4,17]$，而真正的答案序列是 $(2,6),(9,8),(15,12),(17,17)$，两者并不相同——tails 只是"每个长度对应的最小结尾"这张查询表，长度才是答案。最终长度为 4，与样例一致。

代码

Python 版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 02:26
# update_at: 2026-09-30 02:26

import sys
from bisect import bisect_right
from collections.abc import Iterator
from itertools import islice


def read_links(data: Iterator[int], n: int) -> list[tuple[int, int]]:
    """读出 n 对坐标 (南岸, 北岸)，并按南岸坐标升序排列。

    zip(data, data) 复用同一个迭代器，天然把相邻的两个数配成一对。
    """
    return sorted(islice(zip(data, data), n))


def longest_chain(north: list[int]) -> int:
    """求 north 的最长不下降子序列长度。

    tails[k] 记录“长度为 k+1 的不下降子序列”中最小的结尾值，它关于 k 单调不减，
    所以新值 value 接在哪个长度后面可以直接二分。相等也能接（两条航道只是平行不交叉），
    因此插入点取右侧 bisect_right。
    """
    tails: list[int] = []
    for value in north:
        pos = bisect_right(tails, value)
        if pos == len(tails):
            tails.append(value)
        else:
            tails[pos] = value  # 用更小的结尾值换掉旧的，给后面的坐标留出更多空间
    return len(tails)


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    links = read_links(data, n)  # 按南岸排序后，问题变成只看北岸的最长不下降子序列
    print(longest_chain([north for _south, north in links]))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-04 23:37
 * update_at: 2026-10-04 23:37
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 5005;

struct Link {
    ll south; // 南岸坐标
    ll north; // 北岸坐标
};

ll n;
Link link[MAXN];    // 全部友好城市对
ll tails[MAXN];     // tails[k] 表示所有长度为 k+1 的不下降子序列中最小的结尾值
ll tails_len;

// 先按南岸坐标升序，南岸相同时再按北岸坐标升序。
// 这样南岸相同的两条航道（共端点，不算交叉）会自然按北岸递增排列。
bool cmp_link(Link a, Link b) {
    if (a.south != b.south) return a.south < b.south;
    return a.north < b.north;
}

void read_input() {
    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> link[i].south >> link[i].north;
    }
}

// 按南岸排好序后，“航道两两不交叉”等价于北岸坐标单调不下降，
// 于是问题变成在 north 序列上求最长不下降子序列。
// 用 upper_bound 找第一个大于当前值的位置：取右侧插入点，允许相等的值接在后面。
void solve() {
    sort(link + 1, link + n + 1, cmp_link);

    tails_len = 0;
    for (ll i = 1; i <= n; i++) {
        ll value = link[i].north;
        ll pos = upper_bound(tails, tails + tails_len, value) - tails;
        tails[pos] = value;
        if (pos == tails_len) {
            tails_len++;
        }
    }

    cout << tails_len << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    read_input();
    solve();

    return 0;
}

复杂度

• 时间复杂度：$O(n \log n)$——排序 $O(n \log n)$，之后每个元素一次二分 $O(\log n)$；优于标准 $O(n^2)$ 的 DP，$n \leqslant 5000$ 时毫无压力。
• 空间复杂度：$O(n)$——存排好序的点对与 tails 数组。

总结

这道题的难点不在算法，而在建模：把"航道不交叉"这个几何条件，翻译成"按南岸排序后北岸坐标单调不下降"这一条一维条件，题目就退化为经典的最长不下降子序列。具体到一个细节：坐标允许相等，两条共端点或平行的航道不算交叉，因此是不下降（bisect_right）而不是严格上升（bisect_left）——这一点在真实数据里会直接改变答案。最后用 tails 数组加二分把 $O(n^2)$ DP 优化到 $O(n \log n)$，长度即答案。