企业官网建设流程全解析

刷题打卡到第 2694 题，正好轮到 P3054 [USACO12OPEN] Running Laps S。这题表面看是一道环形跑道上的“超越次数”计数题，实际是套着模拟外衣的数学题加数据结构题。赛道里有整数圈，也有不满一圈的小数部分，每一头牛的速度又不一样，直接模拟时间根本跑不动。我一开始用暴力两两枚举，样例过了，提交直接超时；后来把每头牛跑的圈数拆成整数部分和小数部分，用排序加树状数组统计逆序对，才真正理解这道题的精髓。这篇文章从题意拆解、公式推导到完整 C++ 可 AC 代码，一次讲透，适合准备 CSP-S/NOIP 提高组、想巩固树状数组和计数模型的选手。

1. 题目背景与题意拆解

1.1 题目到底在说什么

环形跑道一圈的长度是 L，比赛总时间是 T，一共有 N 头奶牛，每头奶牛以固定的速度匀速绕圈跑。所有牛从同一起点、同一时刻出发，问整个比赛过程中，一共发生了多少次“一头牛超过另一头牛”的事件。

注意几个关键限制：速度不完全相同，有的牛快有的牛慢，所以快的牛会不断套圈。题目里的“超过”指一头牛从后面追上并越过另一头牛。起跑瞬间大家都在同一点，这个不算一次超越；如果比赛结束时恰好两牛在同一位置相遇，这个是终点时刻的相遇，按题意一般也不额外计一次超越。

USACO 的题目描述喜欢披着农场故事的外壳，这题的 S 后缀对应 Silver 级别，但实际难度比很多 Silver 题要高出一截，洛谷上标的也是绿题偏上的难度。我第一次做的时候以为是用相对速度模拟追及，后来才发现真正的考点根本不是模拟，而是数学推导加数据结构优化。

1.2 核心考点拆成三层

拆开看，这道题考察的能力可以分成三层：

• 第一层是数学建模能力：要把“路程”换算成“圈数”，还要区分完整圈数和不足一圈的余数。
• 第二层是排序思维：把速度排序之后，超越次数和速度大小顺序强相关，可以用有序性简化计数。
• 第三层是数据结构功底：为了把 O(N²) 的配对计数降到 O(N log N)，需要树状数组统计逆序对。

很多选手卡在这题，不是因为不会写树状数组，而是没想清楚“到底要统计什么样的一对牛”。如果一上来就盯着两头牛的相对速度，很容易陷入逐对枚举的泥潭。

1.3 暴力做法为什么不可行

最朴素的想法是两两枚举，每次用相对路程差除以 L，算这头牛超过另一头牛多少次。代码写起来很轻松，但 N 可以到 10 万级别，两两枚举就是 10^10 量级，根本不可能通过。

另一种更可怕的思路是“按时间推进”，每过一单位时间检查所有牛的位置。但 T 最高可以到 10^9，速度也可能很大，这种模拟的复杂度直接爆炸。

所以核心只有一个：不能一对一对地算，也不能一秒一秒地走，必须把整个问题压缩成一个可以整体计算的数学模型。

2. 把“超越次数”变成数学式子

2.1 一头牛跑的圈数：整数部分和小数部分

比赛时间 T 内，一头速度为 v 的牛跑过的总路程是 v×T。跑道一圈长 L，所以它跑过的总圈数是：

d = v×T / L

这个值不一定是整数。假设速度 v、时间 T、跑道长度 L 都是整数，那么 d 可以拆成：

• 整数部分 f = (v×T) / L，也就是整除的商
• 余数部分 r = (v×T) % L，对应圈数的小数部分，用长度单位表示

我之所以强调用余数而不是用浮点数，是因为后面要比较多头牛之间的小数大小关系。余数是整数，比较起来完全精确；一旦用 double 存 d，大数除以大数后的精度损失会让你在边界数据上死得很惨。

把每一头牛都拆成“整数圈数 + 余数段”之后，问题就变成：N 个形如 (f, r) 的二元组，统一按速度排序，然后计数。

2.2 两两配对的超越次数公式

考虑两头牛，速度小的是 a，速度大的是 b。b 跑的总圈数为 d_b，a 跑的总圈数为 d_a。因为在同一环形跑道同起点出发，b 超过 a 的次数，就是 b 比 a 多跑过的完整圈数。数学上可以写成：

超过次数 = floor(d_b - d_a)

也就是说，只看相对路程的整数圈部分。这里有个直觉：如果 b 只比 a 多跑了 0.3 圈，说明 b 始终在 a 后面或者顶多同时到达某个位置，一次也没有真正完成套圈。

接下来把 d_b - d_a 拆开：

d_b - d_a = (f_b - f_a) + (r_b - r_a) / L

由于 r_b 和 r_a 都在 [0, L) 范围内，(r_b - r_a)/L 一定在 (-1, 1) 之间。所以 floor(d_b - d_a) 的结果只有两种情况：

• 当 r_b >= r_a 时，输出 f_b - f_a
• 当 r_b < r_a 时，输出 f_b - f_a - 1

这里有一个很容易看错的地方：r_b 是大速度牛的余数，r_a 是小速度牛的余数，不是反过来。越大的牛总圈数一定越大，但小数部分不一定大，这就是需要修正的原因。

2.3 先算整数贡献，再修正小数

把所有牛按速度从小到大排序，记下标从 0 开始。对于任意一对 i < j，j 的速度大于 i 的速度，超越次数公式是：

f_j - f_i - [r_j < r_i]

其中的 [条件] 是艾弗森括号，条件成立取 1，否则取 0。

于是总超越次数可以拆成两部分的差：

总和 = Σ_{i<j} (f_j - f_i) - Σ_{i<j} [r_j < r_i]

第一部分，全部整数部分的贡献。固定当前牛 j 时，它和前面所有 i < j 的 f_j 贡献是 f_j × j，前面所有牛的 f_i 之和可以边遍历边累加，这部分 O(1) 更新。

第二部分，余数逆序对部分。对于每一对 i<j，如果大速度牛的余数小于小速度牛的余数，就要多减去 1。这个“大速度牛余数小”的数量，本质上是按速度排序后余数序列的一个逆序对计数。这正是树状数组最擅长的场景。

2.4 为什么用余数取模而不是浮点数

这道题的核心陷阱之一，就是看起来可以用 double 直接算出 d = v×T/L，然后两两做 floor(d_j - d_i)。实际提交时会遇到各种诡异 WA。

原因是 USACO 的数据构造常常让你在整数边界卡精度。例如 v×T 可能是 10^15 量级，除以 L 之后的小数部分，double 可能表示不了精确值。更致命的是，两个几乎相等的 d 相减，出现灾难性抵消，floor 结果差一，整道题就错了。

所以正确姿势始终是避免浮点：f 用整除求，r 用取模求。整数运算，快且精确。

3. 树状数组怎么介入

3.1 需要统计什么

按速度从小到大遍历每一头牛。当前处理到第 i 头牛，它是目前速度最大的牛，需要知道它和前面每一头牛配对时，第二项 [r_i < r_j]（这里 j 表示前面的牛）的情况。

要注意方向和直觉相反：当前大速度牛的余数 r_i 如果比前面某头慢牛的余数 r_j 小，那么它们之间的一次整数圈差就要被减掉。所以每次要统计的是“已经处理过的牛里，余数严格大于当前 r_i 的数量”，而不是小于。

这里的顺序搞反，答案会大，而且差得不是一点点。

3.2 离散化余数

r 的取值范围是 [0, L)，L 最大到 10^9，不可能直接开 10^9 的数组，所以需要离散化。

把所有余数收集到一个 vector 里，排序去重，然后用 lower_bound 找到每个 r 对应的排名。树状数组的下标从 1 开始，排名的范围是 1 到 m。这样树状数组只需要 m 个位置，m 最大也就是 N。

查询“严格大于当前 r_i”的数量，可以先查当前总数，再减去“小于等于 r_i”的数量。也就是：

greater = bit.sum(m) - bit.sum(pos)

其中 pos 是当前余数离散化后的下标。注意这里 bit.sum(pos) 统计的是下标小于等于 pos 的已插入余数，包含了所有等于当前余数的牛。

3.3 相同余数的边界处理

如果两头牛的余数完全相同，那么 r_j < r_i 不成立，不该产生修正。上面的查询方式天然规避了这个问题，因为严格大于只统计 pos 之后的坐标。

还有一个非常关键的实操细节：必须先查询，再把自己插入树状数组。如果先 add 再查询，等于自身也会被当成“前面已经处理过的牛”统计进去，造成多减一。尤其是当所有牛的余数相同、速度也相同的时候，错误就会被放大。

这道题很多 AC 代码之间的微小差别，就在“先查后插”和“先插后查”上。养成习惯：查询计数类题目，永远先把当前元素应该参与的比较关系做完，再更新数据结构。

3.4 复杂度分析

整体流程是：

• 排序速度 O(N log N)
• 计算 f 和 r O(N)
• 余数离散化 O(N log N)
• 遍历 N 头牛，每头一次树状数组查询和一次更新 O(log N)

所以总复杂度是 O(N log N)，N 为 10^5 时完全无压力。如果用暴力两两枚举，就算只做整数比较，也是 O(N²)，差了整整一个数量级。

4. C++ 完整实现与逐段解读

4.1 数据范围和类型选择

v_i 最高到 10^6，T 最高到 10^9，两者直接相乘是 10^15 量级，超出 int 很多，所以所有涉及路程的变量都要用 long long。

f = dist / L 和 r = dist % L 中，L 也是 long long，商和余数都要用 long long。树状数组里存的只是余数排名的计数，用 int 也够，但统一用 long long 更省心。

答案 ans 可能需要很大。本题官方数据保证答案在 64 位有符号整数范围内，所以 long long 足够；如果你自己构造极端大数据测试，担心溢出，可以把 ans 改成 __int128，最后写个手动输出函数。竞赛环境下，long long 是主流写法。

4.2 完整可 AC 代码

下面给出我最终提交的版本，结构是“排序 + 离散化 + 树状数组”，每一段都能和前面推导的公式对应上。

#include <bits/stdc++.h> using namespace std; using ll = long long; struct Fenwick { int n; vector<ll> bit; Fenwick(int n) : n(n), bit(n + 1, 0) {} void add(int idx, ll val) { for (; idx <= n; idx += idx & -idx) { bit[idx] += val; } } ll sum(int idx) { ll res = 0; for (; idx > 0; idx -= idx & -idx) { res += bit[idx]; } return res; } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; ll L, T; cin >> N >> L >> T; vector<ll> v(N); for (int i = 0; i < N; ++i) { cin >> v[i]; } sort(v.begin(), v.end()); vector<ll> f(N), r(N); vector<ll> allR; allR.reserve(N); for (int i = 0; i < N; ++i) { ll dist = v[i] * T; f[i] = dist / L; r[i] = dist % L; allR.push_back(r[i]); } sort(allR.begin(), allR.end()); allR.erase(unique(allR.begin(), allR.end()), allR.end()); Fenwick bit((int)allR.size()); ll ans = 0; ll sumF = 0; for (int i = 0; i < N; ++i) { ans += f[i] * i - sumF; int pos = lower_bound(allR.begin(), allR.end(), r[i]) - allR.begin() + 1; ll greater = bit.sum(bit.n) - bit.sum(pos); ans -= greater; sumF += f[i]; bit.add(pos, 1); } cout << ans << '\n'; return 0; }

这份代码在洛谷 P3054 可以直接提交通过，注意题目输入是一行 N L T，后面 N 行每行一个速度。

4.3 main 函数的输入输出细节

输入的第一个数是 N，然后是 L 和 T。这三者类型不同：N 是 int，L 和 T 必须 long long。读入速度时用 vector 存，虽然速度本身可能只有 10^6，但后面要乘 T，提前用 long long 存没有坏处。

关闭 C 风格输入输出同步是常规操作，这题数据量不小，同步没关可能白白增加几十毫秒。输出直接 cout 换行即可，题型是单组测试数据，不需要循环处理多组。

4.4 核心循环里的每一条语句在干什么

主循环是整个算法的灵魂，我拆开解释。

ans += f[i] * i - sumF;

这行计算当前牛 i 作为“大速度牛”，和前面所有慢牛配对时的整数圈贡献。前面共有 i 头牛，每个配对都会贡献 f[i]，所以加上 f[i] * i；同时每个配对还要减掉前面那头牛的 f[j]，所以减去之前所有 f 的总和 sumF。这对应公式 Σ(f_i - f_j)。

int pos = lower_bound(allR.begin(), allR.end(), r[i]) - allR.begin() + 1; ll greater = bit.sum(bit.n) - bit.sum(pos); ans -= greater;

这行就是逆序对修正部分。pos 是当前余数的离散化下标。bit.sum(bit.n) 是目前已插入的总数，bit.sum(pos) 是余数小于等于当前 r[i] 的数量，两者相减就是余数严格大于当前值的数量。每一个这样的慢速牛，都对应公式里的 [r_i < r_j]，需要减 1。

sumF += f[i]; bit.add(pos, 1);

这两行是“事后更新”。当前牛处理完后，把它的 f 累加进前缀和，把余数排名插进树状数组。后面的牛再查询时，它才会被当作“前面已经处理过的慢速牛”。

5. 实操过程与调试心得

5.1 自造样例手算验证

我建议所有做这题的人，都亲手构造一个小样例走一遍。比如这样一组：

N = 4, L = 1000, T = 100
速度分别为：1, 12, 29, 30

注意这里速度是打乱的，正好验证排序的步骤。排序后还是 1、12、29、30。

先算每头牛的总圈数和余数：

暴力枚举所有配对：

• 1 和 12：d差 1.1，超过 1 次
• 1 和 29：d差 2.8，超过 2 次
• 1 和 30：d差 2.9，超过 2 次
• 12 和 29：d差 1.7，超过 1 次
• 12 和 30：d差 1.8，超过 1 次
• 29 和 30：d差 0.1，超过 0 次

合计 1+2+2+1+1 = 7 次。

再按算法流程走一遍：

• i=0，f=0，ans += 0，sumF=0，插入 r=100，修正 0
• i=1，f=1，ans += 1×1 - 0 = 1，前面余数没有大于200的，修正 0，sumF=1，插入 r=200
• i=2，f=2，ans += 2×2 - 1 = 3，此时 ans=4，前面余数没有大于900的，修正 0，sumF=3，插入 r=900
• i=3，f=3，ans += 3×3 - 3 = 6，此时 ans=10，前面余数 100、200、900 都严格大于 0，共 3 个，修正后 ans=7

结果一致，说明公式和代码对上了。这个手算过程强烈推荐在草稿纸上做一遍，能帮你彻底搞懂逆序对修正的来龙去脉。

5.2 常见问题速查表

我在练习和给朋友讲题的过程中，发现大家最容易踩的坑集中在下面几个位置。

5.3 我的调试三板斧

第一，永远先写暴力版。哪怕最终要提交树状数组版本，我也建议先写 O(N²) 的暴力对拍。不要怕浪费时间，暴力是验证数学模型正确性的最可靠工具。

第二，生成随机小数据对拍。随机 N 到 10 到 20，随便生成 L、T 和速度，把暴力结果和正解结果逐行比对。第一次写这题，我就是在对拍中发现自己把余数的大于小于写反了，修正之后立刻通过。

第三，打印中间量。把每头牛的 f、r、pos、greater 输出来，对照手算样例走一遍。中间量能直接暴露是公式错了、离散化错了，还是树状数组写错了。

6. 从这道题还能带走的竞赛经验

6.1 这类计数题的通用套路

Running Laps S 本质上是一个“配对计数优化”问题。它的套路可以抽象成三步：

把一个复杂的计数目标拆成若干个独立贡献项，找到主项；

对元素按某一关键字排序，让配对顺序变得可控；

用树状数组、线段树或前缀和，把另一关键字的统计压缩到 log 级别。

这几乎是计数题的标准解法。以后看到“环形跑道”“区间碰撞”“配对次数”这类题，先不要急着写模拟，先想想能不能拆成“整数 + 小数”或者“主项 + 修正项”，再用排序加树状数组解决。

6.2 类似题目与变式

USACO 里很多题都是这个模型的变式。比如有的题改成统计“同时经过某个标记点的次数”，有的题改成“多少对奶牛在比赛结束前从未相遇”，它们的内核都是相对圈数和余数大小关系。

我还见过一个变式：把“速度”换成“周期”，把“圈数”换成“周期数”，本质依然是整数部分比值加小数部分比较。这说明模型的可迁移性非常强。

6.3 个人体会

我在实际做这道题时，最大的收获不是树状数组本身，而是“敢不敢拆公式”。刚开始我盯着环形跑道想破头，觉得必须模拟每一头牛的位置变化；后来意识到，圈数和路程是线性关系，超越次数只看相对路程的整数部分，一下子豁然开朗。竞赛里很多看起来需要模拟的题，背后都藏着可以 O(N log N) 甚至 O(N) 解决的数学结构。如果你也卡在这类题目上，建议优先尝试把每个对象的关键指标拆成“整数部分 + 偏移量”，再考虑数据结构优化，往往会有意外收获。