AcWing 301. 任务安排2

题目传送门

一、分析过程

1、与上题区别

在\(AcWing\) \(300\) 任务安排\(1\)中，我们使用了费用提前计算的技巧，实现了本题平方级别的算法，对于本题增加的数据范围，\(n<=300000\),显然平方级别的算法不足以解决问题，需要想办法在线性\(O(N)\)的时间内解决本题。

2、优化的思路

对于状态转移方程

其中\(0<=j<i\)
联系题意，\(j\)表示的其实是第\(i\)个批次任务的前一个批次任务的最后一个节点,在上一题中，通过遍历每一个可能的节点，然后找到合理的节点\(j\)。

由于在求\(f[i]\)时，\(sc[i]\),\(sc[n]\),\(S\)都是已知量，对式子做下简单变形，(变化的一堆，不变的一堆)得到:

把变化的\(f[j]\),\(sc[j]\)放到了左侧，把一些在确定\(i\)时刻时的常量放到了右侧。

目标：找到合适的\(j\)，使得\(f[i]\)最小

将\(f[j]\)看作\(y\)，\(sc[j]\)看作\(x\)，\(st[i] + S\)看作\(k\)，\(f[i] - sc[i] * st[i] - sc[n] * S\)看作\(b\)，式子就化作了\(y = kx + b\)这样简单的一次函数

因为\(- sc[i] * st[i] - sc[n] * S\)是固定值，所以\(f[i]\)最小时，截距\(b\)也就最小，问题就转化为在所有\((sc[j],f[j])\)构成的点集中，找到一条斜率为\(k=st[i] + S\)的直线，使得截距\(b\)最小。

这不就变成了直线方程\(y=kx+b\)与一个点集的相交问题了吗？用我们学过的凸包知识来优化它了！如果我们动态维护好了凸包，那么就会大大减少计算量！

二、代码逻辑

1、凸包里的内容

凸包里保存的是一个斜率单调递增的队列，它里面装的是二维坐标，也就是\(x=sc[j],y=f[j]\)。

2、出队列头

我们遍历\(i\)的时候，相当于不断的往点集中加点，并且更新凸包。新增加进来的元素当然也是二维坐标，即\(x=sc[j],y=f[j]\)。

在求\(f[i]\)时，只需要找到凸包中第一个大于\(k\)的斜率即可，由于凸包的边的斜率自左向右是递增的，所以我们可以维护一个队列，队头的斜率最小，并且自队头向队尾斜率是递增的。

新二维坐标元素的加入，可能会破坏原来的凸包，因为虽然横坐标\(sc[j]\)是一直增加的，\(y=f[j]\)也是不断增加的，但是

\(C\)点可能是\(C_1\),也可能是\(C_2\),这两种情况下，\(x,y\)都是在增长，但效果完全不一样，凸包的边有可能变成\(ABC_1\),也可能删除\(B\)变成\(AC_2\)

总结：随着\(i\)的不断从左到右变化，每加入一次点，凸包都会产生相应的变化。下个直线方程再来找与凸包的交点时，也需要再次在凸包的队列中找出两个斜率之间的位置。

我们还注意到求\(f[i]\)时候的\(k = st[i] + S\)，随着\(i\)的增加\(k\)也在增加，所以队列中小于\(k\)的斜率肯定也小于后面的斜率\(k\)，不可能成为最优解的，所以在遍历队列找到第一个大于\(k\)的斜率时可以将小于\(k\)的斜率都删掉。

一条线至少有两个点构成，所以只有队列中有不少于两个点的情况下才能出队头，队头存储的是\((sc[q[hh]],f[q[hh]])\)，与后一个点\((sc[q[hh]+1],f[q[hh]+1])\)构成的斜率是\((f[q[hh]+1] - f[q[hh]]) / (sc[q[hh]+1] - sc[q[hh]])\)，当该斜率小于\(st[i] + S\)时就要出队头考虑下一个斜率，为了避免除法实现时需要变形下改为乘法。

  //出队头 注意这里是 hh < tt ，表示最少队列中有两个点的信息！
  while (hh < tt && f[q[hh + 1]] - f[q[hh]] <= (st[i] + s) * (sc[q[hh + 1]] - sc[q[hh]])) hh++;

出队头一方面是为了自小到大找到第一个大于\(k\)的斜率，另一方面是为了删掉小于\(k\)的斜率

2、加入到队列

出完队头就找到了最优解\(j\)，开始更新\(f[i]\)，然后就是将\((sc[i],f[i])\)加入队列，同样是需要比较斜率大小，将该点放在合适的位置使得队列斜率递增，当\((f[i] - f[q[tt]]) / (sc[i] - sc[q[tt]]) > (f[q[tt]] - f[q[tt]-1]) / (sc[q[tt]] - sc[q[tt]-1])\)时才能加入到队尾。

3、出队列尾

为了维护队列的单调性，插入新点\((sc[i],f[i])\)时，如果该点与之前相邻点的斜率不是高于之前队尾的斜率的，就要将队尾的斜率出队，踢出凸包的点集，直至找到一个合适的位置再插入队列。

4、哨兵

单调队列中存储的是点的编号\(i\)，其代表的斜率应该与其更接近队尾的相邻的点构成的斜率，所以初始情况下队头应该有个哨兵节点\(0\)。

  int hh = 0, tt = -1;
  q[++tt] = 0;//加入哨兵

另外，由于计算过程中的乘法可能会爆\(int\)，所以本题的数组定义为\(long\) \(long\)类型，但本题的坑点是：即使使用了\(long\) \(long\)类型，因为公式里面有乘法的原因，依然可能会爆掉，所以还需要在乘法时采用\(\_\_int128\)。

三、实现代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 300010;
LL st[N];       //表示前i个任务完成所需的时间前缀和sum(Ti)
LL sc[N];       //表示前i个任务完成所需的费用前缀和sum(Ci)
LL f[N];        //总费用最小值
int q[N];       //单调队列

int main() {
    int n, s;
    cin >> n >> s;

    for (int i = 1; i <= n; i++) cin >> st[i] >> sc[i], st[i] += st[i - 1], sc[i] += sc[i - 1];
    int hh = 0, tt = -1;
    q[++tt] = 0;//加入哨兵
    for (int i = 1; i <= n; i++) {
        //出队头
        while (hh < tt && f[q[hh + 1]] - f[q[hh]] <= (st[i] + s) * (sc[q[hh + 1]] - sc[q[hh]])) hh++;

        //利用公式更新最优解
        f[i] = f[q[hh]] - (st[i] + s) * sc[q[hh]] + sc[i] * st[i] + s * sc[n];

        /**
        本题之前的数据由于标程溢出long long类型，所以部分数据有误，现已更正。
        大家在做本题时需要注意两个long long类型的数据相乘需要强制类型转化成__int128以避免溢出问题。
         */
        //出队尾
        while (hh < tt &&
               (__int128) ((f[q[tt]] - f[q[tt - 1]]) * (sc[i] - sc[q[tt]])) >=
               (__int128) ((f[i] - f[q[tt]]) * (sc[q[tt]] - sc[q[tt - 1]])))
            tt--;
        //加入
        q[++tt] = i;
    }
    //输出
    printf("%lld\n", f[n]);
    return 0;
}