You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

5.4 KiB

This file contains ambiguous Unicode characters!

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

AcWing 302 任务安排3

一、题目描述

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

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

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

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

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

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

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

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

输入格式 第一行包含两个整数 NS

接下来 N 行每行有一对整数,分别为 T_iC_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 ykx

此处的换元是令


\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_{j1,j}≤k_i<k_{j,j+1}

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

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

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

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

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

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

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

把点插入 队列 前,先要 队列 中 至少有两个点,然后把 满足 k_{q_{tt1}, 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;
}