python/TangDou/AcWing/ConvexHullTrick/302.md

AcWing 302 任务安排3

一、题目描述

有 N 个任务排成一个序列在一台机器上等待执行，它们的顺序不得改变。

机器会把这 N 个任务分成若干批，每一批包含连续的若干个任务。

从时刻 0 开始，任务被分批加工，执行第 i 个任务所需的时间是 T_i。

另外，在每批任务开始前，机器需要 S 的启动时间，故执行一批任务所需的时间是启动时间 S 加上每个任务所需时间之和。

一个任务执行后，将在机器中稍作等待，直至该批任务全部执行完毕。

也就是说，同一批任务将在同一时刻完成。

每个任务的费用是它的完成时刻乘以一个费用系数 C_i。

请为机器规划一个分组方案，使得总费用最小。

输入格式 第一行包含两个整数 N 和 S。

接下来 N 行每行有一对整数，分别为 T_i 和 C_i，表示第 i 个任务单独完成所需的时间 T_i 及其费用系数 C_i。

输出格式 输出一个整数，表示最小总费用。

数据范围 1≤N≤3×10^5,0≤S,C_i≤512,−512≤T_i≤512

输入样例：

5 1
1 3
3 2
4 3
2 3
1 4

输出样例：

153

二、题目分析

本题 相较于 上一题 的不同之处在于：−512≤t_i≤512

该限制使得 t_i 的 前缀和 st_i 不再是 单调递增 的了

我们再来观察一下上一篇中推导的公式：

\large f_i=min(f_j+S \times (sc_n-sc_j)+st_i \times (sc_i-sc_j))

提出常量后的剩余部分：\large f_j-sc_j \times (S+st_i) 换元：\large y−kx

此处的换元是令

\large \left\{\begin{array}{ll}
 f_j=y_j& \\ 
 sc_j=x_j& \\
 k_i=S+st_i
\end{array}\right.

在 上一篇题解 中提到过，点集 上第一个出现在直线 y=kx+b 上的点是 下凸壳 上的点

且满足 k_{j−1,j}≤k_i<k_{j,j+1}

下凸壳 上的点集，相邻两点 构成的 斜率 是 单调递增 的

在上题中，斜率 k(k_i=S+st_i) 也是 单调递增 的，故可以用 单调队列 在 队头 维护 大于k 的 最小值

而本题中，k_i 不具备 单调性，因此不能再用 单调队列 优化了

不过， 下凸壳上的点集，相邻两点构成的斜率是单调递增的

我们可以利用上 单调性，维护一个 下凸壳的点集，则对于 k_i，找到 大于他的最小值 就可以 二分 啦

通过利用一个 队列（非 滑动窗口，故不考虑队列最大长度），完成对于 下凸壳点集 的维护即可

关于如何利用 队列 维护 下凸壳的点集，这在上篇题解中的最后有提到，直接 引用原文 了：

把点插入 队列 前，先要 队列 中 至少有两个点，然后把 满足 k_{q_{tt−1}, q_{tt}} ≥k_{q_{tt},i} 的 点 q_{tt} 弹出 即 新加入的点，必须和 原点集 构成 下凸壳，无效点要先删去 这里我把公式展开，方便大家理解： \large \displaystyle k_{q_{tt-1},q_{tt}}<k_{q_{tt,i}} \Rightarrow \frac{y_{q_{tt}}-y_{q_{tt-1}}}{x_{q_{tt}}-x_{q_{tt-1}}}<\frac{y_i-y_{q_{tt}}}{x_i-x_{q_{tt}}} \Rightarrow \frac{f_{q_{tt}}-f_{q_{tt-1}}}{sc_{q_{tt}}-sc_{q_{tt-1}}}<\frac{f_i-f_{q_{tt}}}{sc_{q_i}-sc_{q_{tt}}} 这样，队列 中 相邻两点 之间构成的直线 斜率单增，也就是我们的 有效下凸壳点集

本题要点：

1. 用队列维护 下凸壳点集
2. 用 二分 找出 点集 中第一个出现在直线上的点

还是要维护下凸壳，但不能删除队列头，因为后面还可能用的上。但有一个好处，就是这仍然是一个单调的队列，可以二分。

三、实现代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 300010;
int n, s;
LL t[N], c[N], f[N];
int q[N];

int main() {
    cin >> n >> s;
    for (int i = 1; i <= n; i++) cin >> t[i] >> c[i], t[i] += t[i - 1], c[i] += c[i - 1];
    // 初始化队列
    int hh = 0, tt = 0; // 添加哨兵

    for (int i = 1; i <= n; i++) { // 动态规划，从小到大枚举每个i
        int l = hh, r = tt;
        // 通过二分upper_bound，找到第一个斜率大于k=st[i] + S的两个点,起点就是切点
        while (l < r) {
            int mid = (l + r) / 2;
            // check函数
            if (f[q[mid + 1]] - f[q[mid]] > (t[i] + s) * (c[q[mid + 1]] - c[q[mid]]))
                r = mid;
            else
                l = mid + 1;
        }

        int j = q[l]; // 切点位置

        // 动态规划
        f[i] = f[j] - (t[i] + s) * c[j] + t[i] * c[i] + s * c[n];

        // 出队尾，斜率比自己大的点都要出凸包队列,小心long long的乘法
        while (hh < tt && (__int128)(f[q[tt]] - f[q[tt - 1]]) * (c[i] - c[q[tt - 1]]) >= (__int128)(f[i] - f[q[tt - 1]]) * (c[q[tt]] - c[q[tt - 1]]))
            tt--;
        q[++tt] = i;
    }
    cout << f[n] << endl;
    return 0;
}