自动搬运

查看原文

来自洛谷，原作者为

	sysulby **

搬运于2025-08-24 22:52:00，当前版本为作者最后更新于2023-11-16 19:34:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先考虑第一个问题：第 $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$ 辆至多会在 $\frac{x_j - d_j - d_{j-1} - \dots - d_{i+1} - x_i}{s_i - s_j}$ 时刻就会撞上前车。

而 $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$。

代码如下：

  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}$。