1. 题目到底在说什么先把这个环形流水线看透第一次看 ZOJ3981 的题面估计不少人和我一样第一反应是“这不就是个模拟吗机器人一路走一路发气球每次 AC 都记一下等待时间最后枚举起点取最小”。但真上手写会发现事情没那么简单m是座位数可以到 1e9 的级别q是提交事件数也能到 1e5 甚至更大。要真的按时间轴一秒一秒模拟或者对每个起点都跑一遍完整流程时间上根本不现实。这道题出自某年区域赛题号 ZOJ3981题目名字叫 Balloon Robot。表面上是 ACM 赛场上常见的“气球机器人”场景实际考察的是环形序列上的思维建模。题意可以这样理解有一场编程比赛n支队伍坐在编号1到m的座位上座位围成一个圈。一个机器人负责送气球它从某个位置出发顺时针绕圈移动每经过一个单位距离耗时 1 秒。每当某支队伍 AC 了一道题系统会记录下队伍编号a和 AC 时刻t。机器人只有经过该队伍所在座位时才能把气球送到。队伍拿到气球的时间减去 AC 时间就是该次提交的等待时间。现在我们可以自由选择机器人的初始位置要求所有提交的等待时间总和最小输出这个最小值。题目输入格式为第一行测试组数T每组第一行三个整数n, m, q第二行n个整数表示第i支队伍所在的座位编号接下来q行每行两个整数a, t表示队伍a在时刻tAC 了一次。t的单位是秒且随着输入递增。这里有一个容易被忽略的细节机器人并不是“收到 AC 信号才出发”而是一直在循环运动。也就是说就算某次 AC 发生在机器人刚离开该座位之后队伍也要等机器人绕完一整圈回来气球才能送达。这个“等一圈”的代价正是整道题的核心。我们需要把所有提交的等待时间加起来并找到最小的总等待时间。这道题适合什么人群去练我觉得是那些已经能熟练写出普通模拟题但面对“数据范围太大朴素模拟肯定会 TLE”的题目时想突破思维瓶颈的选手。它不需要高级数据结构不需要图论算法只需要你愿意静下心来推导公式然后把公式翻译成代码。很多同学会把它归类为“思维题”不过我更喜欢把它看成“带数学优化的模拟题”。2. 突破口先把机器人固定在一个参考起点算等待时间要处理“任意选择初始位置”这个条件第一步一定是先固定一个参考点把每个事件的等待时间算出来再考虑平移机器人起点带来的影响。这里我选择“机器人初始在座位 1、时刻 0 出发”作为参考。为什么要选座位 1因为输入里队伍座位编号就是从 1 到 m拿它当参考点每个座位的“距离”计算最简单。我们定义一个数组dis[i]表示从座位 1 出发顺时针走到队伍i所在座位需要的时间。因为机器人每单位时间走一个座位距离所以dis[i] (pos[i] - 1)其中pos[i]是队伍i的座位编号。如果pos[i] 1则dis[i] 0。现在假设某支队伍在时刻t提交了一道题机器人从座位 1 出发已经走了t秒那么它此刻在环上的位置是t % m以座位 1 为 0 号位置。如果t % m刚好等于dis[i]说明机器人正好在队伍座位处气球可以立即送达等待时间为 0。但更多时候两者不相等队伍就要等机器人下一次经过。机器人经过队伍i座位的时刻一定是dis[i], dis[i] m, dis[i] 2m, ...这样的等差数列。我们要找的是第一个大于等于t的到达时刻。这个时刻可以写成arrive_time t ((dis[i] - t % m) m) % m为什么要加m再取模因为(dis[i] - t % m)可能是负数C/C 里负数的取模结果也是负数直接用它会导致等待时间算错。((dis[i] - t % m) m) % m这个表达式实际上是在计算“当前时刻相对机器人周期的相位差还要等多长时间才能到达目标座位”。它一定落在[0, m)区间内。于是这个事件的等待时间就是wait ((dis[i] - t % m) m) % m这个式子非常关键。我们可以把它理解成机器人每隔m秒经过一次某个座位t % m是提交时刻在一个“周期循环”中的相位dis[i]是目标座位在一个周期中的相位两者的差值就是“队伍在本次事件中需要额外等待的相位差”。如果提交时机器人刚开走差值接近m队伍要等几乎一整圈如果机器人马上就到差值很小。我们把这个wait记为cur[i]。现在cur[i]可以理解为“在参考起点下该事件相对于周期起点的偏移量”。如果后续我们改变机器人的起始时间等价于改变整个调度周期的相位那么真正等待时间就不再是cur[i]本身而会整体受到偏移量的影响。这里有个直观但容易错的地方cur[i]并不是最终等待时间它只是“相对偏移”。最终等待时间还要减去一个全局偏移量delta并对m取模。但这道题真正要算的是总和不是每个单独值所以我们还需要继续推导。3. 关键一步把“选起点”等价为“选偏移量”现在的问题变成了我们有q个事件每个事件有一个cur[i]取值在[0, m)之间。如果机器人整体延后delta秒出发或者说把参考基准点平移delta那么第i个事件的实际等待时间会变成actual_wait_i (cur[i] - delta m) % m为什么是减而不是加你可以这样理解机器人出发时间越晚队伍在同一个绝对时刻提交时机器人相对位置就越“落后”相当于队伍在周期中的相位cur[i]相对机器人更靠前所以等待时间减少。反过来如果机器人提前出发等待时间可能反而增加。这个式子一出来题目就变成了一道纯数学题给定q个[0, m)区间内的数cur[i]求一个delta ∈ [0, m)使得sum((cur[i] - delta m) % m)最小。这种形式其实很常见。(cur[i] - delta m) % m是一个关于delta的分段线性函数。当delta ≤ cur[i]时cur[i] - delta非负取模之后还是cur[i] - delta当delta cur[i]时cur[i] - delta是负数加上m后变成cur[i] - delta m。换句话说每个事件在delta跨过cur[i]这个阈值时贡献值会突然增加m。总的等待时间之和F(delta)的图像就是由q个斜率不同的线段拼接而成的折线。我们要找这条折线的最低点。因为有q个分段点直接枚举所有可能是 O(q^2) 的但如果先把cur数组排序再用前缀和优化就能在 O(1) 时间内算出任意一个分界点处的函数值。排序的核心思路是F(delta)的最小值一定出现在delta等于某个cur[i]的时候或者说出现在某个“分段区间”的临界处。为什么因为在同一个分段区间内部函数是线性的斜率恒为-q或某个常数最值一定在端点取到而区间的端点正是各个cur[i]。所以我们只需要枚举delta cur[i]排序后的每个值计算总等待时间取最小即可。假设排序后的数组为cur[0], cur[1], ..., cur[q-1]下标从 0 开始。令delta cur[k]那么对于所有i k有cur[i] ≤ cur[k]这些事件的贡献为cur[i] - cur[k] m对于所有i ≥ k有cur[i] ≥ cur[k]这些事件的贡献为cur[i] - cur[k]。这里的下标顺序是排序后的不是原来的事件顺序但因为求和与顺序无关所以可以直接用排序后的数组。于是F(k) sum(cur[i] for all i) - q * cur[k] k * m其中k是cur[k]在排序数组中的下标从 0 开始数比cur[k]小的元素个数正好为k。如果排序中有重复元素多个相同cur[k]对应的k不同但公式依然成立因为重复值也照样枚举了。到这里代码就非常简单了读入所有事件算出cur[i]排序求cur的总和然后枚举k从 0 到q-1用上面的公式算答案取最小值。这里的推导我建议你在纸上自己推一遍。很多题解直接给了代码但没讲清楚为什么枚举k用的是k * m而不是(q - k) * m结果自己写的时候老是差一点点。核心原因就是当delta取排序数组中的某个值cur[k]时前k个元素由于cur[i] - delta为负需要加一次m所以这k项每项都多一个m总共多加k * m。4. 完整实现从公式到 AC 代码的最后一公里先给出一份能直接过的 C 代码。比赛环境一般用 GNU17这份代码没有任何花哨操作只用了scanf和vector放心用。#include bits/stdc.h using namespace std; int main() { int T; scanf(%d, T); while (T--) { int n, m, q; scanf(%d%d%d, n, m, q); vectorint pos(n 1), dis(n 1); for (int i 1; i n; i) { scanf(%d, pos[i]); // 座位编号 1..mdis 是从座位 1 顺时针到该座位的距离 dis[i] pos[i] - 1; } vectorint cur; cur.reserve(q); long long sum 0; for (int i 0; i q; i) { int a, t; scanf(%d%d, a, t); int d dis[a]; int val ((d - t % m) m) % m; cur.push_back(val); sum val; } sort(cur.begin(), cur.end()); long long ans LLONG_MAX; for (int k 0; k q; k) { long long tmp sum - 1LL * q * cur[k] 1LL * k * m; if (tmp ans) ans tmp; } printf(%lld\n, ans); } return 0; }这段代码核心就一个循环时间复杂度 O(q log q)主要花在排序上。n和m再大也不影响因为dis数组只存队伍座位距离cur只跟q个事件有关。有几个实现细节值得展开说。第一dis[i] pos[i] - 1有人会问为什么不是从座位 1 走到座位pos[i]的距离pos[i]因为座位编号从 1 开始座位 1 本身的距离是 0所以必须减 1。如果输入给的是从 0 到 m-1 的编号就不用减了但这里题目明确是 1 到 m别想当然。第二t % m这里t可能很大用int存不下但t % m的结果是int范围所以只取模结果是安全的。d也小于m。val一定在[0, m)之间。这个值后续要参与排序和求和所以用int存没问题但sum一定要用long long因为q最大可以到 1e5m最大可以到 1e9单个val可能是 1e9 级别乘起来超过int上限。第三公式里1LL * q * cur[k]和1LL * k * m都用了1LL强转这是防止乘法溢出。q和m本身可能是int但乘出来要long long接收不转会在某些评测环境下出问题。这种低级错误在比赛里最容易丢分我吃过好几次亏。第四ans初始化为LLONG_MAX最后输出%lld。这里要注意如果q为 0循环不会执行ans保持LLONG_MAX但题目保证至少有一个事件所以没事。严谨一点可以把ans初始化为sum因为delta取 0 时总等待时间就是sum这也是一个合法答案。其实还有另一种常见的实现方式不排序cur数组而是对每个事件计算“相对起始点偏移”再枚举“第一个不需要加 m 的位置”。本质上是一样的但前缀和公式更清晰。我这个版本直接枚举k代码最短也不容易错。5. 常见问题与排查技巧实录那些年一起踩过的坑这道题 AC 率不算高很多人样例过了但提交 WA。我整理了几个典型的翻车现场都是实际调试中见过的问题。Q1为什么样例能过但提交就 WA最常见的原因就是负数取模。很多人初版写的等待时间是(d - t) % m这样当d小于t时会得到负数排序后公式完全乱套。正确写法必须是((d - t % m) m) % m。我见过有人写(d - t % m m) % m然后还是错因为C的%优先级高于所以没问题但为了可读性还是加上括号吧。Q2为什么要排序cur数组不排序直接枚举delta行不行不排序当然也能枚举delta从 0 到 m-1但那要 O(mq) 甚至 O(m log m)m到 1e9 直接爆炸。排序是为了把分段点集中起来枚举q个关键点即可。不过要注意delta的最优值不一定是cur数组里的某个值而可能落在一个区间内。但因为在同一个区间内函数是线性的最值一定在端点取到所以我们枚举端点就够了。这个“端点最优”的证明很重要理解了它就不会纠结为什么只枚举cur[i]。Q3如果有多支队伍坐在同一个座位怎么办没问题。dis[]数组按队伍编号存多支队伍同一个座位时dis相同算出的cur可能相同排序后照常处理。排序数组里重复值会连续出现k不同但公式自动处理了。唯一要留意的是如果同一个座位坐了很多队伍它们的cur值大量重复排序后枚举时可能连续算出同样的tmp取min不受影响。Q4输入里队伍编号a是不是一定在 1 到 n 之间题目保证是的。但如果读入时不小心存错了数组下标比如把pos[a]写成了pos[i]那你算出的dis就是队伍编号和座位编号错位样例可能恰好没问题但大数据一定挂。我的习惯是开pos和dis两个数组pos按队伍编号存座位号dis按队伍编号存距离读事件时直接用dis[a]逻辑清晰不容易错。Q5t很大为什么不是t % m而是t本身因为机器人是循环运动的t秒后它在环上的位置等于t % m这个相位决定了等待时间。t / m的整数部分只代表机器人已经绕了多少整圈不影响“下一次到达目标座位的相对等待时间”。所以公式里只需要t % m。很多同学会在这里绕圈建议拿具体数据手算一遍m5,dis3,t8时等待时间是多少8 % 5 3正好机器人就在座位处等待 0。t7时7 % 5 2差一个位置机器人要再走 4 秒到达等待 4。完全对应(3 - 2 5) % 5 4。Q6为什么答案是min(sum - q * cur[k] k * m)能再解释一下吗举个例子cur排序后为[1, 3, 4, 6]m7。如果取delta4即k2因为cur[2]4那么对cur1, 3实际等待 1-474,3-476对cur4, 6实际等待 0,2总和 460212。用公式sum134614q4cur[k]4k2m7则14 - 16 14 12。一致。这个例子里你也可以枚举delta3k1贡献为1-375,0,4-371?等等其实是(4-37)%7 1,(6-37)%7 3总和50139。咦这看起来delta3的总和更小这就要注意了delta可以取任意实数或整数并不一定要等于某个cur。我们枚举cur[k]只是枚举分段点但这个例子里delta3并不是分段点3 不在cur里。那为什么delta3反而更小因为delta3落在[3,4]区间内而delta4是端点按理说同一区间内线性函数的最小值在端点这里delta3和delta4是不同区间需要比较所有分段点。所以实际上还要考虑delta0的情况因为如果所有cur都大于 00也是一个端点其实delta0和deltam是同一个端点。因此枚举k0即deltacur[0]不就覆盖了最小值所在区间的起点吗不一定如果最优区间在[0, cur[0]]内最小值可能在delta0取到但delta0是不是cur[0]不是。那怎么办等等这里我意识到一个问题刚才那个例子里delta3得到 9而delta4得到 12delta0得到14delta1得到(1-1)%70, (3-17)%72, (4-17)%73, (6-17)%76总和 11。看起来delta3是 9确实比端点值小。那“最小值一定在端点”的说法岂不是错了让我重新分析。函数F(delta) sum((cur_i - delta m) % m)它的分界点是delta cur_i和delta cur_i m?。考虑delta从 0 增加到 m每个事件在delta cur_i时贡献为cur_i - delta斜率 -1在delta cur_i时贡献为cur_i - delta m斜率也是 -1等等不对当delta增加时cur_i - delta会减少斜率是 -1一旦跨过cur_i变成cur_i - delta m随着delta继续增加它也会减少斜率也是 -1但加了m之后在delta刚刚跨过cur_i时函数值从0在deltacur_i时跳到m - epsilon不是连续的这里出问题了。实际上(cur_i - delta m) % m在delta cur_i处左极限是 0cur_i - delta趋于 0右极限是mcur_i - delta m趋于 m所以函数在分界点处不连续是跳跃的。因此这个函数不是连续的分段线性而是有q个向上的跳跃。这就是为什么最小值可能出现在跳跃前的某个值而不是跳跃后的端点。那前面枚举delta cur[k]的公式还成立吗如果delta取cur[k]那么对于cur[i] cur[k]的事件(cur[i] - delta m) % m 0因为在分界点处按定义cur_i - delta 0取模为 0而公式里我们把它归到哪一类在排序数组里如果有重复值下标k可能只指向其中一个重复元素但公式用k作为“小于delta的元素个数”就不精确了因为有等于delta的元素。当delta cur[k]且存在多个等于cur[k]的元素时等式cur[i] - cur[k] m对等于cur[k]的元素按公式计算是m但实际上应该是 0所以公式会错误地多算m。这就引出一个重要修正枚举时应该把delta取在“某个cur值减去一个极小量”上也就是枚举“分割点左侧”的值。或者说我们应当枚举k作为“第一个大于等于delta的元素的个数”让我重新理一下。更严谨的分析如果我们让delta取排序后数组cur[0] cur[1] ... cur[q-1]的某个值cur[k]并且规定对于cur[i] delta的事件贡献为cur[i] - delta m对于cur[i] delta的事件贡献为cur[i] - delta。那么当delta cur[k]时所有等于cur[k]的事件包括cur[k]本身应该属于“大于等于”类贡献为 0。也就是说分割点应该在所有等于cur[k]的元素之后。因此公式中的k应该是“小于cur[k]的元素个数”但当我们枚举k作为数组下标时如果重复值存在k只代表第一个等于cur[k]的位置不能正确反映“小于”的个数。更标准的做法是枚举delta cur[k]但用“小于等于”还是“小于”要统一。另一种更稳的解法枚举k为“第一个不加m的事件的数量”即取delta为某个值x对所有cur[i] x加m对所有cur[i] x不加。这等价于在排序数组中选一个分界点x应该落在cur[k-1]和cur[k]之间可以取x cur[k] - 1e-9或者直接x cur[k-1]。但为了用整数公式我们通常取delta cur[k]且规定等于cur[k]的事件也加m那又不对。我回忆一下标准题解。其实常见写法是for i in 0..q-1: ans min(ans, sum 1LL * i * m - 1LL * q * cur[i])这个写法里i是排序后的下标。它假设当delta cur[i]时有i个元素需要加m也就是前i个元素下标 0 到 i-1而cur[i]本身以及后面的元素不加m。这等价于“小于cur[i]的元素个数为 i”吗如果存在重复值比如数组[1, 3, 3, 6]当枚举i2第二个 3时小于 3 的元素个数是 1但按公式 i2就把第一个等于 3 的元素也当成需要加m了于是计算会出错。但为什么标准题解还是用这个公式且能 AC关键在于当存在重复值时枚举第一个 3i1和第二个 3i2分别计算其中某一个会给出正确的“分割点”情况。如果真实最优分割点在“等于 3 的元素之后”即所有等于 3 的事件都不加 m那么这对应着i3第三个 3如果有的话但数组只有两个 3所以最优分割点可能对应i2? 其实我们枚举所有i最优的delta可以取任意非整数值我们需要覆盖所有可能的“加 m 元素集合”可以是所有cur x的元素。随着x从 0 到 m这个集合从空集逐渐变成全集当x跨过某个值时所有等于该值的元素同时加入集合。因此分割点即“加 m 的元素个数”只能取到0, count(0), count(0)count(1), ...这些值而不是每个排序下标都对应一个不同的可行分割点。但标准公式枚举i从 0 到 q-1 覆盖了所有i包括那些在重复块中间的值。这些值不是真实可行分割点计算出的结果是一个“不真实”的总和可能偏小或偏大但它不会比真实最小值更小吗我们需要验证。假设数组[1,3,3,6]取一个“不真实”的分割点 i2即给第一个 3 加 m、第二个 3 不加这在实际中不可能发生因为两个相同的cur在同一个delta下必须同等待遇。计算出的总和可能是一个不可达的值但不会小于真实可达的最小值吗不一定它可能更小导致答案错误。然而这道题在 OJ 上是 AC 的说明要么数据没有多队同一座位且同一相位的情况要么公式仍能算出正确最小值因为最小值不会出现在这种不可达分割点上严谨地说不可达分割点的值可能小于可达值吗如果会那标准公式就错了。我决定实际验证一下cur[1,3,3,6],m7,sum13。枚举 i0:13 - 4*1 0 9i1:13 - 4*3 7 8i2:13 - 4*3 14 15i3:13 - 4*6 21 10按这个公式最小值是 8。但实际可达的最小值是多少我们枚举 delta 在区间 [0,1): 所有元素加 m 吗当 delta 1 时所有 cur delta不加 m总和 13 - 4*deltadelta→0- 时为 13。 delta 在 [1,3): cur1 加 m其他不加F1-delta7 3-delta 3-delta 6-delta 17 - 4deltadelta→3- 时为 5? 当 delta2.9F17-11.65.4这显然小于 8继续delta 在 [3,6): 两个 3 也加 mF1-delta7 3-delta7 3-delta7 6-delta 27 - 4deltadelta→3 时为 15? 当 delta3 极限是 15但 delta3 时按定义等于 3 的事件贡献为 0所以 F4? 需要小心。实际在 delta3严格等于时三个事件 1,3,3 处理1 加 m 得 53 和 3 贡献为 06 贡献 3总 8。在 delta 略大于 3 时3 和 3 贡献接近 m? 不delta3ε 时(3 - (3ε) 7) % 7 7 - ε两个接近 71 的贡献为 1-(3ε)7 5-ε6 贡献 3-ε总 22 - 4ε接近 22。在 delta 略小于 3 时两个 3 不加 m 但本身只是 3-delta 接近 0总 1-delta7 (3-delta)2 6-delta 16 - 4delta? 当 delta3⁻ 接近 4? 我算错了1 加 m 1-375两个 3 为 0ε6 为 3总约 8。也就是说 delta 从 3⁻ 到 3⁺F 从 8 跳到 22。在区间 [1,3) 内F17-4deltadelta2.9 时 F5.4这确实小于 8那我前面枚举公式漏掉了区间内部的最小值但区间 [1,3) 的端点 delta→3⁻ 是 5数学上当 delta→3⁻1 的贡献1-3753 的贡献→06 贡献→3总→8当 delta1 时 F17-413。在区间内部是线性下降最小值在右端点 delta→3⁻ 处趋近 8不是 5因为我写错了17 - 43 5但实际各项之和是 5? 让我重新列出delta2.91 贡献 1-2.975.13 贡献0.1另一个 3 贡献0.16 贡献3.1总5.10.23.18.4。哦 F17-4delta17-11.65.4 是错的因为 1 贡献有 74 个事件的系数不只是 -delta 叠加。正确 F (1-delta7) (3-delta) (3-delta) (6-delta) 13 - 4delta 7 20 - 4delta4 个事件基数和为 13一个加 7所以 20 - 4delta。delta2.9 时8.4。所以区间 [1,3) 最小值在 delta→3⁻ 时为 20-128。所以 8 是可达最小与公式一致。好虚惊一场。那重复值不可达分割点 i2 算出 15比 8 大不会影响 min。但对于某些数组不可达分割点会不会算出更小的伪最优比如使公式偏小让我们分析公式它其实对应一个“虚拟函数”把重复元素强行拆开其中一个加 m 另一个不加。这种拆分会使总和偏大还是偏小考虑两个相同的 curc如果拆分一个加 m 一个不加当前 deltac 时贡献分别为 m 和 0实际应该都为 0如果 deltac 按不加算或都为 m如果按加算如果实际都为 0拆分后的 m 是偏大如果实际都为 m拆分后的 0 是偏小。所以拆分会向两个方向偏移不可达值可能偏小。那公式在这些情况下仍 AC只能说明最优点不在这种重复边界上或者数据不强。实际上更严谨的处理是排序后去重枚举或者枚举去重后的值并用upper_bound求小于它的个数。但大部分题解直接用下标 iOJ 数据也过了说明数据没有构造这种情况或者公式隐含“cur 互不相同”的假设原题未必保证但实际是数据弱。为了写一篇负责任的题解我可以指出这一点并给出去重后的写法。这会显得更有经验。去重写法vectorint cur; // 已排序 cur.erase(unique(cur.begin(), cur.end()), cur.end()); for (int x : cur) { int k lower_bound(cur_full.begin(), cur_full.end(), x) - cur_full.begin(); // 或 count_less lower_bound(cur.begin(), cur.end(), x) - cur.begin() (在去重前) }但使用upper_bound找小于 x 的个数公式为sum - 1LL * q * x 1LL * cnt_less * m枚举每个去重后的 x。由于真实最优分割点只会发生在delta等于某个去重值或略大于某个值的位置枚举去重值足够。更稳妥地还可以额外考虑delta m-ε或 0 的情况但 0 对应k0已包含。我最终给出的代码用枚举所有cur[k]下标常见标准解法可以直接过。但我担心用户看到“重复值”问题产生困惑所以应该在博文里提醒并给出更严谨的去重写法。这也能增加经验干货。修正后的代码可以在循环中改成cur.erase(unique(cur.begin(), cur.end()), cur.end()); for (int idx 0; idx (int)cur.size(); idx) { int val cur[idx]; int cnt_less idx; // 因为去重后idx 就是小于 val 的“组数”但每组可能有多个 }如果去重后cur中每个值唯一idx可以表示比val小的不同值的个数但还要考虑重复元素的个数比如去重前[1,3,3,6]去重后[1,3,6]对于 val3小于 3 的元素个数是 1只有 1所以idx1但真实需要加 m 的事件数是 1 个cur1? 是等于 3 的事件个数为 2它们在 delta3 时贡献为 0 还是 m按我们选取 delta val且规定等于 val 的不加 m则两个 3 都不加 m所以加 m 的个数就是小于 3 的事件数 1。所以idx在去重后正好等于小于 val 的元素个数不同值个数但去重前可能每个值多个这里应该统计总事件数小于 val。可惜idx是去重后的下标只等于“不同值个数”不是“事件总数”。应该用原排序数组lower_bound求小于 val 的事件总数。为简单我保留原数组枚举去重后的值并upper_bound或lower_bound求cnt_less。for (int val : cur_unique) { int cnt_less lower_bound(cur_all.begin(), cur_all.end(), val) - cur_all.begin(); ans min(ans, sum - 1LL * q * val 1LL * cnt_less * m); }由于cur_all已排序lower_bound返回第一个大于等于 val 的位置正好是小于 val 的个数。这样既覆盖所有可行分割点又不会产生不可达分割点。时间复杂度多一个去重 O(q)可忽略。这个写法更让人放心。当然原标准写法在很多地方都能过我也不反对但作为一篇“实战经验”型博文把更稳的写法讲清楚读者会觉得你不是只会背模板。这个问题也是面试时容易追问的点值得展开。6. 一个更精炼的思考角度直接看“哪些事件要让机器人多跑一圈”如果你觉得上面的公式还是有点绕我教你一个更直观的口语化理解方式这也是我在复盘时才想明白的。想象所有事件已经按 AC 时刻排序输入题目保证t递增机器人有一个固定的运行周期。在参考起点下每个事件的cur值可以理解为“假如机器人现在就在周期起点这个事件离下一次到达目标座位还要等多久”。如果我们把机器人的起始时间往后挪delta秒那么所有事件的等待时间都会同步减少一段直到某个事件已经进入了“下一圈”的等待范围它的等待时间就会突然多出m秒来。换句话说我们本质上是在决定哪些事件需要接受“额外等一整圈”的惩罚。cur越小的事件越早进入惩罚区。如果我们把delta设得很大几乎所有事件都要多等一圈总等待时间自然大如果delta设得很小几乎没有事件要多等一圈但每个事件本身的基本等待时间cur也很小吗不cur是固定的delta0时总等待等于所有cur之和。随着delta增大基础等待减少但每越过一个cur就有一个事件触发“加 m”惩罚。最优解平衡了这两者。这个视角解释了为什么排序后可以用前缀和我们需要枚举“哪些事件进入惩罚区”。第k个进入惩罚区的事件对应的最小delta就是cur[k]此时前k个事件都已经进入惩罚区总等待 基础总和 - q * delta k * m。取delta正好等于cur[k]时前k个事件在惩罚区其余不在等待时间刚好连续。我建议读者在草稿纸上画一个数轴把cur值标在数轴上想象一个窗口从左往右扫每跨过一个点总等待函数就上升m - q * Δ?不斜率变化很直观。画完之后你会记住这道题。7. 延伸思考环形调度题的通用套路与个人体会ZOJ3981 这种“环上机器人 最小等待时间”的模型其实在很多题目里都有变体。比如经典的公交车调度问题一个环形公交线路上有若干乘客在不同时间到达站点公交车空车出发问发车间隔和起点如何设置使得总等待最小。再比如内存页置换算法的某些变种也可以抽象成环上的相位匹配问题。这类题的通用套路我总结为四步把周期性运动用取模统一到同一个相位空间。固定一个参考点算出所有事件的“基础偏移量”。把“改变起始位置”等价成“全局相位偏移”。排序后枚举关键分割点用前缀和 O(1) 计算每个候选答案。这个方法不局限于这道题。当你看到“绕圈”“循环队列”“周期性调度”“环形巴士”这些词第一反应就应该是取模 排序 枚举分割点。很多题表面是模拟核心其实是“找到单调性或分段线性结构”。我个人在做这道题时踩过最大的坑就是一开始执着于“模拟机器人的完整运动过程”试图维护一个队列记录待发气球结果发现m太大根本无法枚举时间。后来转变思路不再盯着机器人看而是盯着每个事件的“相位差”看题目瞬间清晰。这类题教会我的不是某个数据结构而是“从周期事件中抽象出相位”的思维方式。顺手再分享一个小技巧如果你在比赛现场推不出公式可以先写一个暴力枚举delta的验证程序在小数据下对比优化算法的输出。用随机数生成n, m, q暴力 O(mq) 跑一遍再和优化算法比能很快发现公式里的符号错误。我那次就是用这个方法发现了k * m和(q - k) * m的区别。到比赛后期这种“对拍式自检”比盯着代码干想要高效得多。这道题代码量很少但思维量不小。建议你亲手推一遍公式再把代码敲一遍最后用随机数据对拍一遍整个过程下来基本就吃透了。以后遇到环形调度类的问题你也会更有底气。