先把暴力写对

实验一里，题目 A 的两种查重写法在四组样例上打出的答案一模一样，跑起来也都是一瞬间。差别出现在大数据那一组：列表查重的版本在十万个数上超时，集合查重的版本一秒都不到。那次是判分脚本把结果摆到面前的——你亲手撞上了它，但没有机会在动手之前判断出来。

这一课要把那次撞车变成一套拿到题就能走的流程。它接在第 2 课后面：第 2 课回答了「这种写法要跑多少次、会不会超时」，这一课回答接下来的那一问——估出来不够快的时候，往哪个方向改。

考场上的正确顺序

拿到一道题，有两种动手顺序。

一种是先想最优解：翻遍脑子里见过的算法，找一个「应该能过」的写法，写出来交上去。这条路的风险在于，最优解往往要在若干种做法之间挑，挑错了就得推倒重来；而时间只够写完一版。另一种顺序是反过来的：先把最直白的枚举写出来，保证它对；再看数据范围，决定它够不够快；不够快，再回头找它哪里做了重复的事。这条路上每一步都有一个已经能跑、答案已经对了的东西在手上，后面的改动是在这个基础上做的。

蓝桥杯按测试点给分。同一道题，小数据那一档和大数据那一档分别算分，所以一版「只能过小数据」的暴力解，本身就握着可观的一部分分数。它的第二个身份在实验一里也见过：几道题放在一起时，暴力解的答案可以拿来和候选解对拍—— 没有标准答案的时候，能互相验证的两个程序里，总得有一个是写起来最笨、最不容易错的那个。

一条走得通的流程

把上面那段话拆开，是一串能逐步落地的动作。每一步都能当场做出判断，不需要灵感。

第 4 步是这套流程的分岔口。估计值没超时限，流程就到此为止——后面三步不用走，这一点在下一节单独说。超过时限，第 5 步才是真正花脑子的地方，而它问的问题很具体：把你第 3 步数出来的那些操作摊开看，哪一部分是同一个东西被算了不止一次。

第 6 步给的交出物是新代码，所以流程会回到第 3 步再来一遍：重新数操作次数、重新估、重新对照时限。改一次不够就再改一次，直到估出来的值落进时限以内。

什么时候不该优化

流程的第 6 步给的是「消掉重复」的几种方向，走到第 5 步才需要挑一个。暴力的估计值没超时限时，第 4 步就已经把流程收住了，正确答案是把这一版交上去。

这个判断在考场上是有分量的。改一版代码要重新验正确性：暴力版是照着定义写的，边界少、容易看穿；优化版多绕了一道，有没有漏掉某种情况、等号该取不该取，都得多测几组才知道。改完还要再花时间确认它没写坏。这些成本是真实的，拿它们去换一段本来就不超时的更快代码，是亏的。

过度设计还有第二种代价：它会挤掉检查的时间。一版改到第三遍的代码，学生往往没时间再回头验样例了。把「能过就先交、过不了再改」当成默认动作，比把「一定要写成最优」当成默认动作稳。

下面这张表把判断收成三行：

案例一：不一样的数

第一个案例就是实验一里那道题，这次把整条流程走完。

第 1 步 · 读规模与时限。 题面给的是 1 \le n \le 2\times10^5，时限 1 秒。

第 2 步 · 写最直白的暴力。 要数这 n 个数里有几个不同的值。最直白的做法是拿一个列表存下已经见过的数，每遇到一个新数就回头看看它在不在这个列表里，不在就加进去：

def brute(a):
    seen = []
    for x in a:
        if x in seen:
            continue
        seen.append(x)
    return len(seen)

这段代码不跳步，也不依赖任何没学过的工具，写完就能确定它是对的。

第 3 步 · 数操作次数。 外层循环跑 n 次。内层的 x in seen 每次要从头扫过 seen，扫的长度从 0 涨到最多 n - 1，平均约 \frac{n}{2}。把每次扫的长度加起来：

n 取 2\times10^5 时，\frac{n(n-1)}{2} \approx 2\times10^{10} 次比较。

第 4 步 · 对照尺子。 本机那把尺子是每秒约 5\times10^7 次基本操作（第 2 课实测，非通用值）， 2\times10^{10} \div 5\times10^7 = 400 秒。时限 1 秒，超了 400 倍。

也可以换个做法，不动手算，直接量一小段再外推。本机实测：

n 从 2 000 到 8 000 是 4 倍规模，暴力版从 0.0099 秒涨到 0.1716 秒，约 17 倍—— 平方档的特征（4^2 = 16）。从 8 000 推到题目给的 2\times10^5 是 25 倍规模，按平方算要慢 25^2 = 625 倍，8 000 那行 0.1716 秒乘上去约 107 秒，稳妥地超过 1 秒时限。

第 5 步 · 找重复做的事。 回头看第 3 步那个求和式 \frac{n(n-1)}{2}。它之所以是平方档，是因为「这个数见过没有」这个问题被反复回答了很多次：每来一个新数就问一遍，而每一次问答都要把 seen 从头扫一遍。 seen 扫完一遍得到的信息，下一个数来时完全用不上，又要从头扫。

用一句话说清这里重复了什么：同一个列表被反复地逐个比过去，而每次问的只是「某个值在不在里面」。

第 6 步 · 消掉重复。 第 3 课量过这件事：问「某个值在不在里面」，列表每次要扫 O(n)，集合平均 O(1)。把 seen 从列表换成集合，问答的次数不变，每次问答的代价从 n 降到常数：

def fast(a):
    seen = set()
    for x in a:
        seen.add(x)
    return len(seen)

回到第 3 步重新数：外层 n 次，内层每次平均 O(1)，总共 O(n)，操作次数约 2\times10^5。第 4 步重新估：2\times10^5 \div 5\times10^7 = 0.004 秒，落在时限以内。

本机实测这一版在 n = 2\times10^5 上跑了 0.0160 秒。两版答案在 n = 10、1\,000、3\,000 上逐一对过，完全一致。同一份数据上两版耗时的比值，n = 8\,000 时是 361 倍。

案例二：数一数有多少对相等

换一道新题，这次从零走完流程。题目是：给定 n 个整数，数一数有多少对下标 (i, j) 满足 i < j 且 a_i = a_j。数据范围 1 \le n \le 10^5，时限 1 秒。

第 2 步 · 写最直白的暴力。 按定义枚举所有数对：

def brute_pairs(a):
    n = len(a)
    count = 0
    for i in range(n):
        for j in range(i + 1, n):
            if a[i] == a[j]:
                count += 1
    return count

第 3 步 · 数操作次数。 外层跑 n 次，内层从 i+1 跑到 n-1，最内层的比较一共做了：

n = 10^5 时约 5\times10^9 次比较。

第 4 步 · 对照尺子。 5\times10^9 \div 5\times10^7 = 100 秒，时限 1 秒，超了 100 倍。

本机实测外推：n = 8\,000 时暴力版 0.6958 秒，从 8 000 推到 10^5 是 12.5 倍规模，按平方算乘 156，约 109 秒。这一次估出来的是同一个结论。

第 4 步的另一半 · 暴力版能拿多少分。 这里要看的是题目的数据分档。 n \le 100 时暴力版的操作次数是 \frac{100 \times 99}{2} = 4\,950 次，一瞬间就跑完； n \le 1\,000 是 499 500 次，同样在时限内。也就是说，n 在几千以内的测试点，这一版全都能过。把这些点先交上去，已经是一部分分数。

第 5 步 · 找重复做的事。 平方档的来源是那两层循环里的同一个比较被反复做： a[i] == a[j] 这一句，对每一对下标都执行一次，而其中大量比较在问同一个问题—— 「这个数值在这个数组里出现了几次」。

把它说得更具体一点。假设某个数值 v 在数组里恰好出现了 3 次，位置是 p_1 < p_2 < p_3。两层循环会分别比较 (p_1, p_2)、(p_1, p_3)、(p_2, p_3)——三次比较，得到的是同一个事实： v 出现了 3 次。而这个事实只要数一遍就够了，数出来是 3，由 3 直接算出对数 \frac{3 \times 2}{2} = 3。暴力的那三次比较，本质上是在用两两比较去重新数一遍一个只需要数一遍的量。

第 6 步 · 消掉重复。 那就把「数一遍」这一步显式地做出来：用字典统计每个数值出现了几次（第 3 课的字典计数），再由每个数值的次数直接算出它对多少对：

def fast_pairs(a):
    counts = {}
    for x in a:
        counts[x] = counts.get(x, 0) + 1
    total = 0
    for c in counts.values():
        total += c * (c - 1) // 2
    return total

回到第 3 步：第一遍循环 n 次，字典查找与写入平均 O(1)；第二遍循环次数等于不同数值的个数，不超过 n。总共 O(n)，操作次数约 2\times10^5。第 4 步重新估：2\times10^5 \div 5\times10^7 = 0.004 秒，通过。

本机实测：

两版答案在 n = 10、1\,000、3\,000 上都一致（n = 3\,000、取值 1 到 50 时都是 89 596）。

这一课的两个案例，优化的动作不同，找重复的思路是同一个：

把重复做的事看见

上面两个案例里，「重复」都是靠数循环次数推出来的。这一节把它做成能跑的对照： 同一件事的两种做法，把内层到底执行了多少次打印出来。

数一数「比较操作」发生了几次。暴力版把所有数对都枚举一遍，优化版只把每个元素看一遍：

def brute_ops(n):
    ops = 0
    for i in range(n):
        for j in range(i + 1, n):
            ops += 1
    return ops

def fast_ops(n):
    ops = 0
    for i in range(n):
        ops += 1
    return ops

for n in (10, 100, 1000, 10000):
    print(n, brute_ops(n), fast_ops(n))

本机跑出来的结果：

$ py count_ops.py
10 45 10
100 4950 100
1000 499500 1000
10000 49995000 10000

n 从 10 涨到 10 000 是一千倍，暴力版从 45 涨到 49 995 000，约一百一十万倍。速度差就是这样长出来的：规模涨一千倍，平方档涨一百万倍。

两个版本之间的差距，从 4 倍、49 倍、499 倍一路涨到 4 999 倍。这个数字比秒数更可靠——它不随机器变，只随 n 变。在动手之前用纸笔把它算出来，就是流程第 3、4 步在做的事。

【题目】给定 n 个整数 a，找出其中最大的一对（两个不同的下标 i ≠ j），输出它们的和。
【规模】1 ≤ n ≤ 10^5；时限 1 秒。

这一课用到的判断

配套项目「AI 刷题助手」在这里对应的是最实的一段：给出候选写法之前，它得先按数据范围判断哪一版能过，再决定推荐暴力解还是优化解，并说明为什么。这个判断就是上面那六步。

• OI Wiki · 复杂度本课数操作次数与估耗时用的口径：基本操作数、\Theta 与 O 的区别、哪些量算常量
• Python 官方文档 · time练习里的实测照它写：perf_counter() 是单调时钟，前后相减就是这段代码的耗时
• Python 官方教程 · 数据结构5.4 集合、5.5 字典：案例一把 seen 从列表换成集合的依据
• 实验一 · 把一道题跑通案例一那道题与它的判分数据，两条线索对照着看