AcWing 302 任务安排3

题目传送门

一、题目分析

在\(AcWing\) \(301\) 任务安排\(2\)中，我们给出了任务安排问题的斜率优化的解法，因为斜率\(k = st[i] + S\)是单调递增的(直线与横轴的夹角递增)，所以队列中小于当前\(k\)的斜率一定小于后面的\(k\)，于是我们在查找第一个大于\(k\)的斜率时将小于\(k\)的斜率都删除了，从而保证了\(O(n)\)的时间复杂度。

但是本题的\(T_i\)可能是负数，尽管时间是负数设置得有些不合理，我们只能暂且认为它是合理的，\(T_i\)是负数时，\(k = st[i] + S\)就未必单调递增了，因为前缀和不一定单调递增了，这意味着，后面的\(k\)可能小于之前的\(k\)，我们不应该在寻找第一个大于\(k\)的斜率时删掉小于\(k\)的斜率了，因为后面的\(k\)还可能用到，但是不删除小于\(k\)的斜率，意味着每次寻找\(j\)都需要从堵头找起，时间复杂度最坏可能是平方级别的，为此我们在找第一个大于\(k\)的斜率时，只能对队列中的斜率做二分查找，用\(O(nlog_n)\)的时间复杂度去解决本题了。本题的其它代码与上题一致，故分析过程可以参考上题，唯一修改的地方就是将原来出队头的代码修改为二分找\(j\)的代码了。

二、实现代码

#include 

using namespace std;

typedef long long LL;
const int N = 300010;
int n, s;
LL st[N], sc[N];
LL f[N];
int q[N];

int main() {

    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 = 0;

    for (int i = 1; i <= n; i++) {
        int l = hh, r = tt;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (f[q[mid + 1]] - f[q[mid]] > (st[i] + s) * (sc[q[mid + 1]] - sc[q[mid]])) r = mid;
            else l = mid + 1;
        }

        int j = q[l];
        f[i] = f[j] - (st[i] + s) * sc[j] + st[i] * sc[i] + s * sc[n];
        while (hh < tt && (double) (f[q[tt]] - f[q[tt - 1]]) * (sc[i] - sc[q[tt - 1]]) >=
                          (double) (f[i] - f[q[tt - 1]]) * (sc[q[tt]] - sc[q[tt - 1]]))
            tt--;
        q[++tt] = i;
    }
    printf("%lld\n", f[n]);
    return 0;
}