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.

12 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 301. 任务安排2

一、题目描述

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

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

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

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

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

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

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

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

输入格式 第一行包含整数 N

第二行包含整数 S

接下来 N 行每行有一对整数,分别为 T_iC_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的,因此ABBC_1构成了一个下凸壳;

尾部出队列的判定

② 如果新加的点不是C_1而是C_2BC_2的斜率小于AB,那么ABBC_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_3ABBC能够作为下凸壳,当且仅当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_jsc_j×(S+st_i)

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

\large f_jsc_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) 写成 yx(j) 写成 x,但是请读者心中明白,这两个 变量,都是关于 j变量

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

直线方程 进行变形:b=ykx

要求 ykx (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_jkx_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_{j1,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_{tt1},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;
}