python/TangDou/AcWing/ConvexHullTrick/301.md

AcWing 301. 任务安排2

一、题目描述

有 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,1≤T_i,C_i≤512,0≤S≤512

输入样例：

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

输出样例：

153

二、凸包优化【斜率优化】

这类问题做的过程比较偏数学

对于状态转移方程需要经过一些数学上的整理,之后几道题步步深入 斜率优化 问题

在AcWing 300 任务安排1中，使用了 费用提前计算 的技巧，实现了 平方级算法 ，本题数据范围:n<=300000,平方级算法不足以解决问题，需要 更牛X 的算法。

引入前导知识 凸包:

1、凸包概念

如图所示，点集 中 外层的点 组成的 凸多边形 就构成了能够包含所有点的 凸包

• ① 相邻的边,斜率越来越小 的一组点叫做 上凸壳
• ② 相邻的边,斜率越来越大 的一组点叫做 下凸壳

2、凸包维护

如图:

① 开始只有顶点AB构成的 凸包，然后加入第三点C_1，显然BC_1的斜率是高于AB的，因此AB，BC_1构成了一个下凸壳；

尾部出队列的判定

② 如果新加的点不是C_1而是C_2，BC_2的斜率小于AB，那么AB和BC_2就不能构成下凸壳了，因为不能作为点集的下边界，不能包含在AB下面却在AC_2上面的点，因此，加入C_2后，AC_2将成为下凸壳新的边界了。

为了维护好下凸壳，新加入的点C_2，在未加入队列前，先检查队列头中元素A与要新加入点之间的斜率k_{A,C_2},和队列中第一个、第二个点之间的斜率k_{A,B},如果k_{A,C_2}<k_{A,B} ,则从尾部弹出B点，所有符合这样条件的点弹出后，再把新点C_2入队列。

对于平面上的三点A(x_1,y_1),B(x_2,y_2),C(x_3,y_3)，并且x_1 < x_2 < x_3,y_1 < y_2 < y_3。AB与BC能够作为下凸壳,当且仅当AB的斜率要小于BC的斜率。

3、利用凸包优化

朴素版的 状态转移方程：

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

当讨论到f_i时，st_i,sc_i,S \times sc_n都是固定值、常数，变化的是含j描述字样的数据项,提出式子中 含有单独 i 的常量：

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

考察 min 函数内部的 多项式：f_j−sc_j×(S+st_i)

我们知道 含 i 的项是一个 常量，故该 多项式 就能够 抽象 成如下形式：

\large f_j−sc_j×(S+st_i)=变量1−变量2×(常量S+常量i)

注意:这里的 变量1 和 变量2 并不是两个 独立变量 ,变量1 f_j 是与 j 有关的 变量，变量2 sc_j 也是与 j 有关的 变量

因此，不妨令 $ \left{ \begin{array}{ll}
f_j=y(j)\ sc_j=x(j)\ k=S+st_i \end{array} \right. ,则该函数可以化为:$y(j)-k\cdot x(j)

为了式子 方便观察，接下来我会把 y(j) 写成 y，x(j) 写成 x，但是请读者心中明白，这两个 变量，都是关于 j 的 变量

求 y−kx (0≤j<i)函数的极值问题，可以直观想到 直线方程：y=kx+b

对 直线方程 进行变形：b=y−kx

要求 y−kx (0≤j<i) 函数的极值，就是求在 所有可能 的 点集 (x,y) 中，找到一个点 (x_j,y_j) 与当前 k_i 构成的 所有直线 中，y轴截距最小,转化为 斜率固定的直线与某一个点集 之间的关系

一共有i对数,即i个点:

\large (sc[0],f[0]),(sc[1],f[1]),...,(sc[i-1],f[i-1])

也就是在求上述 点集 与 当前斜率固定 为k=S+st_i的直线 相交 时，最小的截距b 是多少。

看图说话：

华罗庚：数缺形时少直观，形少数时难入微，数形结合百般好

图中，黑色点 为所有 0≤j<i 的点 (x_j,y_j)，红色线 为 斜率 是 k_i 的 直线

我们 从下往上（截距从小到大） 去逼近当前 点集中的点 则 第一个 出现在直线上的点，就是满足 b_i=y_j−kx_j 的 最小截距 b_i，即是当前阶段 DP 的 最佳策略

那么，如何有效的维护点集呢？

这就是一个 线性规划 的问题了：在 点集 中，找到一个 点，绘制 固定斜率 的直线，使得 截距最小

由 线性规划 知识可知：我们只用考虑 点集 中 凸壳 上的点即可

解读:直线由下向上逼近，肯定先碰上下凸壳，肯定不会先碰上再往上的点集,告诉我们，其实只要维护好下凸壳就行，凸壳以上的点集既然用不到，就没必要计算，都没必要计算了，就没必要维护。

几何直观 上，显然这题要维护的是 下凸壳

因此，对于任意的 f_i 来说，我们只需去寻找 下凸壳 上的 点 构成 直线 的 最小截距 即可

这样 时间复杂度 在 最坏 的情况下，还是 O(n^2)（即 所有点 的 (x,y) 单增，k_1<k_2<k_3,全部点集 构成一个 下凸壳）

斜率优化了个寂寞？并非如此！我们再看看直线方程中，各参数的性质

由于 t_i,c_i 都是 正整数，故它们的 前缀和 st_i,sc_i 是 单调递增的

对应于 直线方程的参数：x_j=sc_j 是 单调递增 的，k_i=S+st_i 也是 单调递增 的

而 下凸壳 中 相邻两点 构成的直线 斜率 也是 单调递增 的

则 下凸壳 中第一个出现在 直线 上的点，满足：k_{j−1,j}≤k_i<k_{j,j+1}，此时 直线截距 b_j 最小 (大家可以配合下图几何直观理解该处的不等式)

头部出队列的判定：

而又由于 k_i 单调递增，所以 j 之前 的 点 都不会是 点集 中出现在 直线 上的 第一个点

此时 只需维护点集区间 [j,i] 的 点 即可，直到 k_{j,j+1}≤k<k_{j+1,j+2} 时，维护点集区间 变为 [j+1,i]

根据上述所说，出现了我们最熟悉的模型-滑动窗口模型

故我们可以直接利用 单调队列 来维护 下凸壳中的 有效点集

并用队头的 前两个点:j_1=q_{hh},j_2=q_{hh+1} 维护 大于当前斜率 k_i 的最小斜率 \large k_{q_{hh} , q_{hh+1}}

这里我把公式展开，方便大家理解：

\LARGE k_{q_{hh},q_{hh+1}}>k_i \Rightarrow \frac{y_{q_{hh+1}}-y_{q_{hh}}}{x_{q_{hh+1}}-x_{q_{hh}}} >k_i \Rightarrow \frac{f_{q_{hh+1}}-f_{q_{hh}}}{sc_{q_{hh+1}}-sc_{q_{hh}}} >S+st_i

把点插入 单调队列 前，先要保证 队列 中 至少有两个点，然后把 满足 \large k_{q_{tt−1},q_{tt}}  ≥k_{q_{tt},i} 的 点 q_{tt} 弹出

即 新加入的点，必须和 原点集 构成 下凸壳， 无效点删除

这里我把公式展开，方便大家理解：

\LARGE 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_i-sc_{q_{tt}}}  

这样，队列 中 相邻两点 之间构成的直线 斜率单增，也就是我们的 有效下凸壳点集

4、【技巧】防止丢失精度

∵ y_1 = kx_1+b ~~~① ~~~~y_2 = kx_2+b ~~~② 联立①② y_1-y_2=kx_1-kx_2 ∴ k=(y_1-y_2)/(x_1-x_2)

避免除法丢失精度： ∴ y_1-y_2=k(x_1-x_2)

三、实现代码

时间复杂度： O(n)

Code

#include <bits/stdc++.h>

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

int main() {
    int n, s;
    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++) {
        /*
        Q:为什么是 hh < tt ?
        A:队列中最少有两个元素，才能考虑计算斜率，才能开始出队头
        队列中一个元素,hh=0,tt=0
        队列中两个元素,hh=0,tt=1 这样的情况下，保证了最少有一条边，才有斜率概念

        (1) k=st[i]+S 所有数据是正数，所以k是单调递增的
        (2) k从下向上移动，找到与点集的第一个交点，必然在下凸壳上
        (3) 在相交时，其实是与三个点组成的两条直线进行相交，设 a,b,c，能够相交的必要因素是K_{a,b}<k<K_{b,c}
        (4) 双向队列其实是一个单调上升的队列
        (5) 双向队列中只保留斜率比当前ki大的下凸壳点集，比ki斜率小的点，以后也不会再使用，在i入队列前，删除掉
        */

        // 队列头中的q[hh]其实是就是优解j,使得截距f[i]的值最小
        // 要保证随时从队列头中取得的数，是下凸壳中第一个从k=st[i]+s大的,原来有比k小于等于的点都可以剔除了
        while (hh < tt && f[q[hh + 1]] - f[q[hh]] <= (t[i] + s) * (c[q[hh + 1]] - c[q[hh]])) hh++;

        // Q:为什么在未入队列前更新？
        // A: 因为i是在查询它的前序j,找到了使它最小的j就对了，现在队列头中保存的就是使i最小的前序j,当然是放入队列前进行更新
        f[i] = f[q[hh]] - (t[i] + s) * c[q[hh]] + c[i] * t[i] + s * c[n]; // 利用公式更新最优解

        // 出队尾:现在凸包里记载的两个点之间斜率大于新加入值的清理掉
        while (hh < tt && (f[q[tt]] - f[q[tt - 1]]) * (c[i] - c[q[tt]]) >= (f[i] - f[q[tt]]) * (c[q[tt]] - c[q[tt - 1]])) tt--;
        q[++tt] = i;
    }
    // 输出
    cout << f[n] << endl;
    return 0;
}