洛谷 P11511 [ROIR 2017 Day 2] 大型直线对撞机 题解
duanxinghe
·
·
题解
洛谷 P11511 [ROIR 2017 Day 2] 大型直线对撞机题解
题目概括：
在一根无限长的数轴上，有 n 个粒子，它们各有两种状态，分别是正负两种，正电子向数轴正方向运动，负电子像数轴负方向运动，速度都为 1。当正电子和负电子相撞，则会消失。问：当 t_i 秒时，数轴上还有多少粒子。
分析：
由于 x_i 的给出是单调递增的，所以我们不难发现，输入时，若是一个负电子，那么与它最先发生碰撞的就是离它最近的被输入进来的正电子，那么我们就一定知道每个粒子消失的时间（如果它会消失的话）。
那么如何维护呢？那当然会想到栈，每次遇到一个正电子就将它放进栈中，那么在栈顶的一定就是后输入进来的正电子，每输入一个负电子我们就将栈顶的正电子弹出去，然后计算它们的相撞时间 a_i。
设栈顶元素坐标为 x_j，当前元素坐标为 x_i。
a_i = \frac{x_i - x_j + 1}{2}
最后进行模拟，先将 a_i 数组从小到大进行排序，定义一个标记变量 now 表示枚举到 a 数组的第 now 位，如果 a 数组的第 now 位 \le t_i 就说明这两个粒子在 t_i 前就已经被消失了，所以 now 就往后移，同时答案减 1。
由于有些粒子从一开始就不会被消失，所以就设它们的时间为无穷大。
代码：
说明：我的代码是看了这位大佬的题解，至于我的代码，也不知道什么原因惨痛爆 0，所以代码在此就不放了。