P9807：斜率优化预处理 + 事件排序扫描

· · 题解

首先考虑第一个问题：第 i 辆车在什么时刻撞上前车？

我们先假设已经完成计算，并记录该时刻为 t_i（后面会讨论 t_i 的计算方法）。

想象按 t_i 的顺序遍历事件，所有车辆会逐渐连接在一起，形成若干辆“小火车”。在这一过程中，对于每节车（也就是初始的每辆车），可以用并查集维护所在小火车的车头。

考虑向右并线的情况，当且仅当在超过某辆火车头的时刻（不妨记录为 e_i），向右不会撞到前一辆小火车的车尾。

因此，将所有的 t_i 与 e_i 放到一起按时间排序扫描：

代码如下：

  vector<pair<long double, int> > events;
  for (int i = 1; i <= n; i++) {
    events.emplace_back(t[i], -i);
    events.emplace_back(e[i], +i);
  }
  sort(events.begin(), events.end());
  int ret = 1; // 超过第 n 辆车一定可以并线，提前设为 1
  for (auto &[t, i]: events) {
    if (i < 0) {
      i = -i;
      fa[i] = find(i + 1);
    } else {
      if (i < n && find(i) == i) {
        int j = find(i + 1);
        if (sgn(s[0] * t - (x[j] + s[j] * t - len[j] + len[i])) <= 0) ret++;
      }
    }
  }
  cout << ret << '\n';

然后再看 t_i 的处理。

不妨记第 i 辆车的速度为 s_i，如果第 j 辆车满足 i < j 且 s_i \gt s_j，则第 i 辆至多会在

而 $t_i$ 则相当于，对于所有满足条件的 $j$，上式的最小值。 直接 $O(n^2)$ 暴力计算，可以解决 $n \leq 1000$ 的子任务。 接下来考虑如何优化。 不妨记 $d_i$ 的前缀和为 $len_i$，则上式可以整理为 $\frac{(len_i - x_i) - (len_j - x_j)}{s_i - s_j}$，显然是斜率关系。 同时可以发现，在从大到小遍历 $i$ 的过程中，$len_i - x_i$ 单调递增！ 因此可以使用单调栈维护左凸壳，利用类似斜率优化 DP 的实现方式，$O(n)$ 计算所有的 $t_i$。 代码如下： ```cpp deque<int> deq; for (int i = n; i >= 1; i--) { t[i] = 1e100; // x: s[i] // y: len[i] - x[i] auto on_left = [&]() { int j = deq.back(), k = deq[deq.size()-2]; double x1 = s[j] - s[k], y1 = (len[j] - x[j]) - (len[k] - x[k]); double x2 = s[i] - s[k], y2 = (len[i] - x[i]) - (len[k] - x[k]); return sgn(x1 * y2 - x2 * y1) >= 0; }; while (deq.size() >= 2 && on_left()) deq.pop_back(); if (!deq.empty()) { int j = deq.back(); if (sgn(s[i] - s[j]) > 0) t[i] = (x[j] - x[i] - len[j] + len[i]) / (s[i] - s[j]); } deq.push_back(i); } ``` --- 最后，建议在判断浮点数大小关系时，设置 $eps = 10^{-8}$。