自动搬运

查看原文

来自洛谷，原作者为

	Makab 我什么都做不到！

搬运于2025-08-24 22:32:44，当前版本为作者最后更新于2025-04-25 17:32:30，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

题解

先考虑暴力。

设 $f_i$ 表示开始制造第 $i$ 辆车的最早时间（有边界 $f_1 = 0$），$g_i = \sum \limits_{j = 1}^{i} t_i$，$h$ 为原题目中的 $f$，那么有如下转移：

$$f_i = f_{i - 1} + \max \limits_{j = 1}^{n} (g_j \cdot h_{i - 1} - g_{j - 1} \cdot h_i) $$

可做如下理解：

• 工人 $j$ 处理完毕第 $i - 1$ 辆车的时刻为 $f_{i - 1} + g_j \cdot h_{i - 1}$；
• 工人 $j$ 开始处理第 $i$ 辆车的时刻为 $f_i + g_{j - 1} \cdot h_i$；
• 由题意，有 $f_i + g_{j - 1} \cdot h_i \ge f_{i - 1} + g_j \cdot h_{i - 1}$， 即 $f_i \ge f_{i - 1} + g_j \cdot h_{i - 1} - g_{j - 1} \cdot h_i$，对所有工人取最大值。

答案即为 $f_m + g_n \cdot h_m$。这样的时间复杂度为 $\mathcal O(N^2)$，考虑斜率优化。

引入 $k = \frac{h_i}{h_{i - 1}}$，则原式化为：

$$\begin{aligned} f_i &= f_{i - 1} + \max \limits_{j = 1}^{n} (g_j \cdot h_{i - 1} - g_{j - 1} \cdot (k \cdot h_{i - 1})) \\ &= f_{i - 1} + h_{i - 1} \cdot \max \limits_{j = 1}^{n} (g_j - k \cdot g_{j - 1}) \\ \end{aligned} $$

进一步地：

设点集 $P_i = (g_{i - 1}, g_i), (1 \le i \le n)$，令 $y_i = k \cdot x_i + b_i$。

给定斜率 $k$，求使得 $y_j - k \cdot x_j$ 最大，即 $b_j$ 最大的一个 $j$。

那么，对于点集 $P$，维护一个上凸壳，每次二分地求斜率为 $k$ 的直线与之的切点即可，时间复杂度 $\mathcal O(N \log N)$。

代码

constexpr int N = 1e5 + 2;

int n, m, stk[N], top;
/**
 * f[i]: 第 i 辆车最早开始处理的时刻;
 * g[i]: 前 i 个工人的系数前缀和;
 * h[i]: 第 i 辆车的系数;
 */
ll f[N], g[N], h[N];

double slope(int i, int j) { return (double)(g[i] - g[j]) / (g[i - 1] - g[j - 1]); }

int main() {
    read(n, m);
    rep(i, 1, n) read(g[i]), g[i] += g[i - 1];
    rep(i, 1, m) read(h[i]);
    rep(i, 1, n) {
        while (top > 1 && slope(i, stk[top]) > slope(stk[top], stk[top - 1])) --top;
        stk[++top] = i;
    }
    rep(i, 2, m) {
        int l = 0, r = top, mid;
        double k = (double)h[i] / h[i - 1];
        while (l < r) {
            mid = (l + r) / 2;
            if (slope(stk[mid + 1], stk[mid]) > k) l = mid + 1;
            else r = mid;
        }
        f[i] = f[i - 1] + g[stk[l]] * h[i - 1] - g[stk[l] - 1] * h[i];
    }
    printf("%lld\n", f[m] + g[n] * h[m]);
    return 0;
}