Slope Trick

cforrest · 2025-04-13 03:13:53 · 题解

首先注意到

因此，同一段路的能量消耗只与传送带速度 s，移动距离 \Delta L 和移动时间有关 \Delta t，与 v 的变化曲线无关。所以，不妨假定同一条传送带上，v 是一个常数。

由此，设 f(i,E_i) 为第 i 条传送带开始位置具有能量 E_i\ge 0 的人移动到终点的最小移动时间，可以列出动态规划问题为：

且能量转移需要满足条件：

终值条件为 f(I,\cdot)\equiv 0，即无论最终能量为多少，最小移动时间都是 0。

因为只涉及线性函数和最值，考虑 Slope Trick。每次转移都相当于如下两步骤：

1. 插入一段斜率为 -1/(1+s_i) 的斜率段，长度为 \Delta L_i/(2+s_i)+\Delta L_i/s_i，并将整体左移 -\Delta L_i/s_i；
2. 删掉 0 左侧的部分，即斜率最小的、长度为 \Delta L_i/s_i 的那些斜率段。（因为 E_i\ge0）

最后结束时需要计算 f(0,0) 的值。因为能量充分大时，每段都可以取最大速度 v=2，就有

然后，自右向左把斜率段弹出，累加每段的时间增加值即可。

那些没有传送带的部分自然视为 s_i=0，但是插入时不能真的插入长度为无限大的一段再删掉 0 左侧的部分。注意到，它们的斜率本就是最小的，所以插进去 \Delta L_i/2+\Delta L_i/0 长度的一段之后，还要弹出斜率相同且长度为 \Delta L_i/0 的一段，就相当于直接插入了长度为 \Delta L_i/2 的一段。

核心代码如下：

int main() {
    int n, L;
    std::cin >> n >> L;
    std::vector<std::array<long double, 2>> walkways;
    walkways.reserve(n << 1);
    int x = 0;
    for (int i = 0; i < n; ++i) {
        int l, r;
        long double s;
        std::cin >> l >> r >> s;
        if (l > x) {
            walkways.push_back({ (long double)(l - x), 0.0l });
            x = l;
        }
        walkways.push_back({ (long double)(r - l), s });
        x = r;
    }
    if (x < L) {
        walkways.push_back({ (long double)(L - x), 0.0l });
        x = L;
    }
    std::priority_queue<std::array<long double, 2>> slopes;
    double res = 0.0;
    for (int i = walkways.size() - 1; i >= 0; --i) {
        auto [len, s] = walkways[i];
        if (s < 1e-10l) {
            slopes.push({ 1.0l, len / 2 });
            res += len / 2;
        } else {
            slopes.push({ 1 / (1 + s), len / (2 + s) + len / s });
            long double excess = len / s;
            while (excess > 1e-10) {
                auto [k, d] = slopes.top();
                slopes.pop();
                if (excess - d >= 0) {
                    excess -= d;
                } else {
                    slopes.push({ k, d - excess });
                    excess = 0.0;
                }
            }
            res += len / (2 + s);
        }
    }
    while (!slopes.empty()) {
        auto [k, d] = slopes.top();
        slopes.pop();
        res += k * d;
    }
    std::cout << std::fixed << std::setprecision(12) << res;
    return 0;
}

时间复杂度为 O(n\log n)。