|
|
|
|
|
## [$AcWing$ $301$. 任务安排$2$](https://www.acwing.com/problem/content/description/303/)
|
|
|
|
|
|
### 一、题目描述
|
|
|
|
|
|
|
|
|
|
|
|
有 $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$
|
|
|
|
|
|
|
|
|
|
|
|
**输入样例**：
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
|
|
|
5
|
|
|
|
|
|
1
|
|
|
|
|
|
1 3
|
|
|
|
|
|
3 2
|
|
|
|
|
|
4 3
|
|
|
|
|
|
2 3
|
|
|
|
|
|
1 4
|
|
|
|
|
|
```
|
|
|
|
|
|
|
|
|
|
|
|
**输出样例**：
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
|
|
|
153
|
|
|
|
|
|
```
|
|
|
|
|
|
|
|
|
|
|
|
### 二、凸包优化【斜率优化】
|
|
|
|
|
|
|
|
|
|
|
|
这类问题做的过程比较偏数学
|
|
|
|
|
|
|
|
|
|
|
|
对于状态转移方程需要经过一些数学上的整理,之后几道题步步深入 **斜率优化** 问题
|
|
|
|
|
|
|
|
|
|
|
|
在[$AcWing$ $300$ 任务安排$1$](https://www.cnblogs.com/littlehb/p/15818491.html)中，使用了 **费用提前计算** 的技巧，实现了 **平方级算法** ，本题数据范围:$n<=300000$,平方级算法不足以解决问题，需要 **更牛$X$** 的算法。
|
|
|
|
|
|
|
|
|
|
|
|
引入前导知识 **凸包**:
|
|
|
|
|
|
|
|
|
|
|
|
#### 1、凸包概念
|
|
|
|
|
|
|
|
|
|
|
|
<center><img src='https://img-blog.csdnimg.cn/20200303193435786.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMwMjc3MjM5,size_16,color_FFFFFF,t_70'></center>
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
如图所示，**点集** 中 **外层的点** 组成的 **凸多边形** 就构成了能够包含所有点的 **凸包**
|
|
|
|
|
|
* ① 相邻的边,**斜率越来越小** 的一组点叫做 **上凸壳**
|
|
|
|
|
|
* ② 相邻的边,**斜率越来越大** 的一组点叫做 **下凸壳**
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
#### 2、凸包维护
|
|
|
|
|
|
|
|
|
|
|
|
<center><img src='https://img-blog.csdnimg.cn/20200303194514325.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMwMjc3MjM5,size_16,color_FFFFFF,t_70'></center>
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
如图:
|
|
|
|
|
|
|
|
|
|
|
|
① 开始只有顶点$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$** 是多少。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
看图说话：
|
|
|
|
|
|
|
|
|
|
|
|
<center><img src='https://cdn.acwing.com/media/article/image/2021/09/25/55909_306884c91d-Xnip2021-09-25_11-46-08.jpg'></center>
|
|
|
|
|
|
|
|
|
|
|
|
>**华罗庚：数缺形时少直观，形少数时难入微，数形结合百般好**
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
图中，**黑色点** 为所有 $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$ 最小 (**大家可以配合下图几何直观理解该处的不等式**)
|
|
|
|
|
|
|
|
|
|
|
|
<center><img src='https://cdn.acwing.com/media/article/image/2021/09/25/55909_374d8dc11d-IMG_C28104BF5784-1.jpeg'></center>
|
|
|
|
|
|
|
|
|
|
|
|
#### 头部出队列的判定：
|
|
|
|
|
|
|
|
|
|
|
|
而又由于 $k_i$ **单调递增**，所以 **$j$ 之前** 的 **点** 都不会是 **点集** 中出现在 **直线** 上的 **第一个点**
|
|
|
|
|
|
|
|
|
|
|
|
此时 <font color='red' size=4><b>只需维护点集区间</b></font> $[j,i]$ 的 **点** 即可，直到 $k_{j,j+1}≤k<k_{j+1,j+2}$ 时，**维护点集区间** 变为 $[j+1,i]$
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
根据上述所说，出现了我们最熟悉的模型-**滑动窗口模型**
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
故我们可以直接利用 **单调队列** 来维护 **下凸壳中的** <font color='red' size=4><b>有效点集</b></font>
|
|
|
|
|
|
|
|
|
|
|
|
并用队头的 **前两个点:$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}$ 弹出
|
|
|
|
|
|
|
|
|
|
|
|
即 **新加入的点**，必须和 **原点集** 构成 **下凸壳**， <font color='red' size=4><b>无效点删除</b></font>
|
|
|
|
|
|
|
|
|
|
|
|
这里我把公式展开，方便大家理解：
|
|
|
|
|
|
$$\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$
|
|
|
|
|
|
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
|
|
|
#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;
|
|
|
|
|
|
}
|
|
|
|
|
|
```
|
