专栏文章

Slope Trick

ccforrest
CF1209H题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipmrao1
此快照首次捕获于
2025/12/03 14:32
3 个月前
此快照最后确认于
2025/12/03 14:32
3 个月前
查看原文
首先注意到
ΔE=∫tt+Δt(1−v)dt=Δt−(ΔL−sΔt).\Delta E = \int_{t}^{t+\Delta t}(1-v)dt = \Delta t - (\Delta L-s\Delta t).
因此，同一段路的能量消耗只与传送带速度 ss，移动距离 ΔL\Delta L 和移动时间有关 Δt\Delta t，与 vv 的变化曲线无关。所以，不妨假定同一条传送带上，vv 是一个常数。
由此，设 f(i,Ei)f(i,E_i) 为第 ii 条传送带开始位置具有能量 Ei≥0E_i\ge 0 的人移动到终点的最小移动时间，可以列出动态规划问题为：
f(i,Ei)=min⁡v∈[0,2]f(i+1,Ei+1)+Ei+1−Ei+ΔLi1+si,f(i,E_i) = \min_{v\in[0,2]}f(i+1,E_{i+1})+\dfrac{E_{i+1}-E_i+\Delta L_i}{1+s_i},
且能量转移需要满足条件：
Ei+1=Ei+1−vv+siΔLi≥0.E_{i+1} = E_i + \dfrac{1-v}{v+s_i}\Delta L_i\ge 0.
终值条件为 f(I,⋅)≡0f(I,\cdot)\equiv 0，即无论最终能量为多少，最小移动时间都是 00。
因为只涉及线性函数和最值，考虑 Slope Trick。每次转移都相当于如下两步骤：
  1. 插入一段斜率为 −1/(1+si)-1/(1+s_i) 的斜率段，长度为 ΔLi/(2+si)+ΔLi/si\Delta L_i/(2+s_i)+\Delta L_i/s_i，并将整体左移 −ΔLi/si-\Delta L_i/s_i；
  2. 删掉 00 左侧的部分，即斜率最小的、长度为 ΔLi/si\Delta L_i/s_i 的那些斜率段。（因为 Ei≥0E_i\ge0）
最后结束时需要计算 f(0,0)f(0,0) 的值。因为能量充分大时，每段都可以取最大速度 v=2v=2，就有
f(0,+∞)=∑iΔLi2+si.f(0,+\infty)=\sum_i\dfrac{\Delta L_i}{2+s_i}.
然后，自右向左把斜率段弹出，累加每段的时间增加值即可。
那些没有传送带的部分自然视为 si=0s_i=0，但是插入时不能真的插入长度为无限大的一段再删掉 00 左侧的部分。注意到，它们的斜率本就是最小的，所以插进去 ΔLi/2+ΔLi/0\Delta L_i/2+\Delta L_i/0 长度的一段之后，还要弹出斜率相同且长度为 ΔLi/0\Delta L_i/0 的一段，就相当于直接插入了长度为 ΔLi/2\Delta L_i/2 的一段。
核心代码如下：
CPP
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(nlog⁡n)O(n\log n)。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...