|
|
|
|
|
## [$AcWing$ $302$ 任务安排$3$](https://www.acwing.com/problem/content/304/)
|
|
|
|
|
|
|
|
|
|
|
|
### 一、题目描述
|
|
|
|
|
|
有 $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$
|
|
|
|
|
|
|
|
|
|
|
|
**输入样例**：
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
|
|
|
5 1
|
|
|
|
|
|
1 3
|
|
|
|
|
|
3 2
|
|
|
|
|
|
4 3
|
|
|
|
|
|
2 3
|
|
|
|
|
|
1 4
|
|
|
|
|
|
```
|
|
|
|
|
|
|
|
|
|
|
|
**输出样例**：
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
|
|
|
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. 用 **二分** 找出 **点集** 中第一个出现在直线上的点
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
还是要维护下凸壳，但不能删除队列头，因为后面还可能用的上。但有一个好处，就是这仍然是一个单调的队列，可以二分。
|
|
|
|
|
|
|
|
|
|
|
|
### 三、实现代码
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
|
|
|
#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;
|
|
|
|
|
|
}
|
|
|
|
|
|
```
|
