贵萌兄先说结论：P3407“散步”这道题，我第一眼看到以为是个模拟题，差点直接开一个 while(t--) 暴力跑，还好瞟了一眼数据范围及时收手。暴力模拟在大数据下必炸，真正的解法是把它变成“找停靠点 + 二分匹配”的问题。这篇博文就把完整的推导过程、C++ 实现、以及我实际提交时踩过的坑一次讲清楚，适合正在准备信奥、平时用洛谷或各大 OJ 刷题、想系统掌握“碰撞类问题”做法的朋友。
1. 第一反应全是坑：为什么不能直接模拟
1.1 数据范围逼你放弃模拟
拿到题，题目描述很直白：一条路上有 n 个人，第 i 个人初始在 x_i 位置，方向是向左或向右，所有人速度都是每秒 1 个单位。只要两个人同一时刻到达同一位置，他们就都停下来，问 t 秒后每个人在哪里。
乍一听，这不就是最朴素的模拟题吗？每秒移动一下，判断一下有没有人重合，重合就标记停住，t 秒后输出。如果你真的这么写，n 小的时候没问题，但信奥题的数据范围从来不会让你舒服。P3407 的 n 可以到 1e5 级别，t 也可以到 1e9 级别。每秒模拟一次，光时间维度就是 1e9，更别说还要每步检查人和人之间的距离，复杂度直接没法看。
暴力模拟还有一个隐藏问题：你以为“停下来”是终态，但后面的人可能继续走到停住的人身边，然后也停下来，形成连锁反应。如果只用普通的模拟，这种链式反应很难高效处理，每新增一个停住的人，可能又要重新扫描全场。
所以说，这题第一关不是代码能力，而是能不能识别出“模拟不可行”。看到 1e5 和 1e9，第一反应应该是：一定有数学规律或者更巧妙的贪心结构。
1.2 速度恒为 1，位置是线性函数
在没发生碰撞的情况下，每个人的位置可以很简单地算出来。
如果第 i 个人向右走，那么 t 秒后他的无碰撞位置是：
x_i + t
如果向左走，则是：
x_i - t
注意，方向是固定的，速度是恒定的 1，所以每个人的轨迹就是一条斜率为 +1 或 -1 的直线。既然轨迹是直线，碰撞的本质就是两条直线在 t 秒内有没有交点，如果有，交点坐标是多少。
这给了我们一个非常重要的视角转换：不需要真的让时间一帧一帧走，直接比较“如果大家都不停，最终会走到哪里”，然后看哪些人的轨迹线会相交。
1.3 相遇只可能发生在相向而行的两人之间
这里有个很朴素的结论：同方向的人速度相同，永远追不上，所以同向的人之间不会因为“追上”而相遇。只有一个人向右走、另一个人向左走，两个人面对面，才可能在某个时刻到达同一个位置。
举个例子：i 在左边向右走，j 在右边向左走，初始位置 x_i < x_j。它们相遇的条件很简单，就是两者之间的初始距离，要在 t 秒内被两个人相向走完：
x_j - x_i ≤ 2t
因为两个人每秒合计靠近 2 个单位。
如果这个条件满足，那么它们相遇的时刻是：
(x_j - x_i) / 2
相遇位置是：
(x_i + x_j) / 2
这个中点公式非常关键，后面所有代码都是围绕它展开的。
需要模型API调用？ 免费领10W Token，多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 停靠点从哪来：相邻“右左对”是唯一源头
2.1 相邻右左对的相遇点公式
我们把所有人按照初始位置从左到右排序。如果排序后，第 i 个人向右走，第 i+1 个人向左走，也就是出现了一个“右左相邻对”，而且它们之间的距离满足：
x_{i+1} - x_i ≤ 2t
那么这两个人一定会在中点相遇并停下来。这个中点就是一个“停靠点”，坐标是：
(x_i + x_{i+1}) / 2
注意，这里使用的是排序后相邻的两个人。为什么一定要相邻？因为如果中间还隔着别人，那么真正先相遇的往往是更靠内的人，而不是隔着人的这一对。
我举个例子：位置是 1、2、3、4，方向分别是右、右、左、左。虽然位置 2 的“右”和位置 4 的“左”之间距离也满足相遇条件，但它们中间隔着位置 3 的人。事实上，位置 2 和位置 3 会先在中点 2.5 相遇停下来，位置 4 向左走，也会被这个已经停靠的点挡住。所以计算停靠点时，只需要考虑排序后相邻的“右左对”。
2.2 为什么只看相邻就够：中间人优先碰撞
有人可能会问：如果我和右边某个向左走的人能相遇，但中间隔了好几个人，为什么不能直接算我和那个人的相遇点？
关键在于中间人的存在会改变整个过程。
思路是这样的：假设你现在向右走，右边远处有一个人向左走，理论上你们会在某个点相遇。但是你和那个向左走的人之间，只要存在任意一个向右走的人，那么你们三个人中，必然有一对相邻的“右左”会先相遇，从而形成一个新的停靠点。这个停靠点会挡在你和远处那个向左走的人之间，你根本走不到原本的相遇点。
从代码实现的角度看，我们只需要从左到右扫描排序后的数组，一旦发现：
- 当前人是向右走
- 下一个人是向左走
- 两者距离 ≤ 2t
就把它们的中点记录为一个停靠点。
这里还有一个额外的好处：所有停靠点的坐标是天然递增的，因为我们是按位置从左到右扫描出来的，后面记录的停靠点一定在前面的右边。这个递增性质后面二分时直接用得上。
2.3 用两倍坐标存中点，避免 .5 浮点
相遇点可能是整数，也可能是半整数。比如 x_i = 1，x_{i+1} = 2，那么中点是 1.5。如果直接用 double 存，输出时可能会出现精度问题，而且信奥判题时浮点输出往往容易因为精度边界被卡。
解决办法很经典：所有坐标都乘以 2 来存。中点原来的坐标是 (x_i + x_{i+1}) / 2，乘以 2 后就是：
x_i + x_
直接是一个整数，完美避开浮点。
同理，每个人最后的位置如果是停靠点，就存停靠点的两倍坐标；如果没停，就存无碰撞位置的两倍坐标。最后输出时判断一下奇偶：偶数说明是整数坐标，直接除以 2；奇数说明是半整数，输出整除结果加 .5。
3. 链式反应：停靠点像“黑洞”一样吸人
3.1 停靠点会吸收左侧的右行者和右侧的左行者
现在我们已经有了若干个停靠点，但题目没说完：两个人在中点停下后，后续走过来的人也会停下。
举一个最简单的链式反应例子：
位置 1、2、3，方向是右、右、左，t 很大。
先看位置 2 和位置 3，它们是相邻右左对，距离 1，一定会在 2.5 处相遇停下。位置 1 的人向右走，走到 2.5 时，会发现位置 2 的人已经停在那里，于是也停下来。所以最终三个人都停在 2.5。
这种情况下，位置 1 的人并没有直接参与“右左对”的计算，但他确实被停靠点吸收了。
规律总结出来是这样：
- 一个向右走的人，如果他的初始位置在某个停靠点左边，并且以他的速度能在 t 秒内到达这个停靠点，那么他最终会被这个停靠点吸住。
- 一个向左走的人，如果他的初始位置在某个停靠点右边，并且能在 t 秒内到达这个停靠点，那么他最终也会被这个停靠点吸住。
翻译成公式：
向右走的人，初始位置为 x，停靠点位置为 p，需要满足：
x < p 且 p - x ≤ t
向左走的人，需要满足：
x > p 且 x - p ≤ t
3.2 多个停靠点同时满足时，怎么选
“吸住”这个规则看起来简单，但有一个问题：如果一个人同时满足多个停靠点的吸收条件，他该停在哪一个？
想清楚这个问题，可以想象真实的物理过程。
一个向右走的人，从初始位置出发，从左往右走。他会先遇到坐标更小的停靠点，然后才遇到坐标更大的停靠点。所以如果他同时被多个停靠点“吸引”，他一定先撞上最左边那个。一旦撞上，就停下来，根本走不到后面的停靠点。
换句话说，向右走的人，应该选择满足条件的停靠点中坐标最小的那个。
反过来，向左走的人从右往左走，应该选择满足条件的停靠点中坐标最大的那个。
这个规则其实非常符合直觉：不是看哪个停靠点“更配”，而是看哪个停靠点“先被走到”。
3.3 时间上的严谨性：为什么到达时停靠点已经形成
有人可能会担心一个细节：一个向右走的人到达停靠点 p 的时候，p 处的人真的已经停下来了吗？如果 p 处的人还没停，那到头来会不会变成三个人在同一个瞬间相遇，产生新的不同结果？
我们单独看形成停靠点 p 的那一对相邻右左对：右边的向左者叫 L，左边的向右者叫 R。它们相遇的时刻是：
t1 = (x_L - x_R) / 2
假设现在有一个更左边的向右者 K，初始位置 x_K < x_R。K 到达 p 的时刻是：
t2 = p - x_K = (x_R + x_L) / 2 - x_K
因为 x_K < x_R，所以：
t2 - t1 = x_R - x_K > 0
也就是说，形成停靠点的那两个人一定会先相遇停下，之后 K 才姗姗来迟。这种情况下，K 撞上的是一个已经静止的停靠点，结果不会改变。
对向左的人可以对称证明：从右边来的人，也一定晚于停靠点的形成时刻到达。
所以“选中坐标最小的停靠点”这个规则不仅物理上合理，时间上也严格自洽，不会出现“我先到了，但停靠点还没形成”的矛盾。
4. C++ 完整实现：核心代码逐行拆解
4.1 结构体设计、读入与排序
因为最后要按输入顺序输出，而处理过程需要按位置排序，所以我用结构体存每个人，并记录 id。这样排序后计算完，还能按 id 恢复到原始顺序。
cpp复制#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Person {
ll x; // 初始位置
int dir; // 1 向右，-1 向左
int id; // 输入顺序
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
ll t;
cin >> n >> t;
vector<Person> p(n);
for (int i = 0; i < n; ++i) {
cin >> p[i].x;
p[i].id = i;
}
for (int i = 0; i < n; ++i) {
int d;
cin >> d;
p[i].dir = (d == 1 ? 1 : -1); // 根据题目输入调整，1 向右，0 向左
}
sort(p.begin(), p.end(), [](const Person& a, const Person& b) {
return a.x < b.x;
});
// 题目一般保证 x_i 严格递增，但排序更稳妥
读入格式我按“先全部位置，再全部方向”处理。如果你的 OJ 输入是每个位置后面紧跟方向，改成同一个循环里读两个值就行，核心逻辑完全不变。
方向这块很容易弄混，我自己的习惯是代码里统一用 1 表示向右，-1 表示向左，读入时做一次映射，后续逻辑只认 1 和 -1，不认题目里的 0 和 1，这个习惯能少踩很多坑。
4.2 构造停靠点数组
排序之后，从左到右扫描，把所有相邻右左对的中点记录下来。注意这里用的“两倍坐标”：直接存 p[i].x + p[i+1].x，含义是中点坐标的两倍。
cpp复制 vector<ll> stops; // 停靠点的两倍坐标，天然递增
for (int i = 0; i + 1 < n; ++i) {
if (p[i].dir == 1 && p[i + 1].dir == -1) {
ll gap = p[i + 1].x - p[i].x;
if (gap <= 2 * t) {
stops.push_back(p[i].x + p[i + 1].x);
}
}
}
stops.erase(unique(stops.begin(), stops.end()), stops.end());
判断条件 gap <= 2 * t 用的是两倍时间，对应原始条件 x_{i+1} - x_i <= 2t。
有人可能会觉得 2 * t 可能溢出 int，所以 t 和位置一律开 long long。这个习惯在做坐标类题目时非常关键，不是小题大做，而是 1e9 级别的数据乘 2 以后真的会超出 int 范围。
去重这步理论上不会触发，因为不同相邻右左对形成的中点一般不同。不过加上去重也不吃亏，万一某组数据构造出相同中点，也不至于让后面的二分出错。
4.3 二分匹配每个行人
停靠点数组是递增的，所以可以用二分。
向右走的人，找坐标大于自己位置的最左停靠点。用 upper_bound 找到第一个大于 2 * x 的停靠点，然后判断距离是否在 t 秒内能到达。
向左走的人，找坐标小于自己位置的最右停靠点。用 lower_bound 找到第一个大于等于 2 * x 的位置，它前面的那一个就是小于自己的最大停靠点。
cpp复制 vector<ll> ans2(n, 0); // 两倍坐标答案，按 id 存
for (int i = 0; i < n; ++i) {
if (p[i].dir == 1) {
// 向右：选左边最近，也就是坐标大于自己的最小停靠点
auto it = upper_bound(stops.begin(), stops.end(), 2 * p[i].x);
if (it != stops.end() && *it - 2 * p[i].x <= 2 * t) {
ans2[p[i].id] = *it;
} else {
ans2[p[i].id] = 2 * (p[i].x + t);
}
} else {
// 向左：选右边最近，也就是坐标小于自己的最大停靠点
auto it = lower_bound(stops.begin(), stops.end(), 2 * p[i].x);
if (it != stops.begin()) {
--it;
if (2 * p[i].x - *it <= 2 * t) {
ans2[p[i].id] = *it;
continue;
}
}
ans2[p[i].id] = 2 * (p[i].x - t);
}
}
这段代码就是整个解法的核心，其实加起来不超过 20 行。二分条件里，*it - 2 * p[i].x 是向右的人到停靠点的两倍距离，要小于等于 2 * t，也就是原始距离要小于等于 t。
有人可能会问：如果停靠点数组为空怎么办？upper_bound 和 lower_bound 会正常返回 end() 或 begin()，程序会走 else 分支，输出无碰撞位置，完全没问题。
4.4 输出：奇偶判断半整数
最后按 id 恢复原始顺序，输出两倍坐标转换后的结果。偶数直接除以 2，奇数输出 x.5。
cpp复制 for (int i = 0; i < n; ++i) {
if (ans2[i] % 2 == 0) {
cout << ans2[i] / 2 << '\n';
} else {
cout << ans2[i] / 2 << ".5\n";
}
}
return 0;
}
如果题目要求输出一位小数，也可以用 printf("%.1f\n", ans2[i] / 2.0)，但用整型判断奇偶在信奥里更稳，既不会被浮点精度坑，输出速度也快。
5. 压测与出题人最喜欢的卡法
5.1 手工验证几个典型场景
写完之后，我习惯先跑几组手造数据，不直接交题。这里分享几组我当时用来验证的例子，每一组都对应一个容易出错的场景。
第一组：基本无碰撞。
输入：
text复制2 3
1 100
1 0
1 号向右走，3 秒后到 4；2 号向左走，3 秒后到 97。两者距离 99，远大于 6，所以不会相遇。输出应该分别是：
text复制4
97
第二组：一对直接相遇。
text复制2 3
1 5
1 0
两者距离 4，小于 6，中点是 3。输出应该都是：
text复制3
3
第三组：链式反应。
text复制3 100
1 2 3
1 1 0
位置 1、2 向右，位置 3 向左。相邻右左对是位置 2 和位置 3，中点是 2.5。位置 1 向右走，也会被 2.5 吸住。输出：
text复制2.5
2.5
2.5
第四组：多停靠点并存。
text复制5 100
1 2 3 4 5
1 1 0 1 0
位置 2 右和位置 3 左形成停靠点 2.5，位置 4 右和位置 5 左形成停靠点 4.5。位置 1 的右行者在 2.5 被吸住，不会跑到 4.5。输出：
text复制2.5
2.5
2.5
4.5
4.5
这组数据能验证“向右选最左停靠点”的规则，如果写成“选第一个满足条件的停靠点”可能没问题，但如果写成“选满足条件中坐标最大的”，位置 1 的人就会错误地跑到 4.5。
5.2 三个容易踩的坑
第一个坑是方向映射。题目里如果规定 0 表示向左，1 表示向右，我一开始曾经写过 if (d == 1) dir = 1; else dir = 1; 这种离谱的手误。建议读入方向后立刻打印一遍，或者干脆把方向的含义写进变量名里，比如 isRight，不要用裸的 0 和 1。
第二个坑是 2 * t 溢出。t 最大到 1e9 时，2 * t 就是 2e9，虽然还在 int 范围内，但如果后面还有坐标相加，比如 p[i].x + p[i+1].x，两个 1e9 相加就已经超过 int 了。所以坐标、时间、答案全部用 long long，别在信奥题里赌 int 不会爆。
第三个坑是二分的边界。向左走的人找“小于自己坐标”的停靠点时，lower_bound 返回的是第一个大于等于自己的位置，如果这个位置刚好是 begin()，说明自己左边没有停靠点，这时不能做 --it 操作，必须先判断 it != stops.begin()。我最早写这段时忘了这个判断，结果在找不到左停靠点的数据上直接 RE。
6. 从 P3407 带走的通用套路
6.1 碰撞类问题的常用化简角度：先算候选，再处理连锁
P3407 这类问题有一个通用的处理模式：不要真的模拟碰撞过程，而是先把所有可能产生停靠点的“候选事件”找出来，然后通过某种规则处理连锁反应。
在这道题里，候选事件就是排序后的相邻右左对。找到候选事件后，停靠点的位置就固定了，剩下的问题只是“谁能到达这个停靠点”。这种化整为零的思路，其实在很多 OI 题里都有变体。
以后遇到“两个人/两个车/两个粒子相遇后停下”的题，第一反应可以是：候选相遇点有哪些？哪些人会被同一个相遇点吸收？是否可以用二分、排序、栈来快速匹配？
6.2 先找不变式，再写代码
这道题还有一个更朴素的启发：写代码之前，先想清楚什么变了，什么没变。
人虽然一直在动，但速度恒定，方向恒定，所以无碰撞轨迹是确定的直线。停靠点一旦形成，它的位置就不会再变。这些“不变”的性质，才是算法能够成立的根基。
我见过很多同学拿到题就开写，结果越写越乱，最后变成一个大模拟。如果面试或比赛时遇到这类题，不妨先在草稿纸上画几个人、几条轨迹，标注出碰撞点和停靠点，画完你可能会发现，答案已经浮出水面了。
6.3 给刷题者的建议
刷信奥题，尤其是洛谷上这些经典题，千万不要用“我看过题解了”来代替“我自己推一遍”。P3407 的题解可能五分钟就能看完，但里面“相邻右左对”这个关键观察，需要自己用笔推导才能变成自己的直觉。
我的建议是：看完题解后，合上屏幕，自己在纸上把这几个场景画一遍：
- 两个右一个左
- 一个右两个左
- 右、右、左、左、右、左
画完以后再自己默写一遍二分匹配的代码。等你哪天遇到一道完全陌生的碰撞题，能下意识想到“先找相邻右左对”，这道题才算真正吸收了。
最后再分享一个我实际做题时的习惯：交题之前，先用一个小脚本生成随机小数据，再写一个暴力模拟程序对拍。P3407 这种题，暴力程序很容易写，几秒钟就能跑完小数据。对拍个几百组随机数据，比你盯着代码看半天更有可能发现隐藏 bug。当年我就是靠对拍抓出了二分边界的问题，省下了一次无谓的 WA。