特拉卡

Makab · 2025-04-25 17:32:30 · 题解

题解

先考虑暴力。

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

可做如下理解：

• 工人 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}}，则原式化为：

进一步地：

设点集 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;
}