302 任务安排3（斜率优化）

布满荆棘的人生 2022-09-15 12:26 185阅读 0赞

**1. 问题描述：**

有 N 个任务排成一个序列在一台机器上等待执行，它们的顺序不得改变。机器会把这 N 个任务分成若干批，每一批包含连续的若干个任务。从时刻 0 开始，任务被分批加工，执行第 i 个任务所需的时间是 Ti。另外，在每批任务开始前，机器需要 S 的启动时间，故执行一批任务所需的时间是启动时间 S 加上每个任务所需时间之和。一个任务执行后，将在机器中稍作等待，直至该批任务全部执行完毕。也就是说，同一批任务将在同一时刻完成。每个任务的费用是它的完成时刻乘以一个费用系数 Ci。请为机器规划一个分组方案，使得总费用最小。

**输入格式**

第一行包含两个整数 N 和 S。接下来 N 行每行有一对整数，分别为 Ti 和 Ci，表示第 i 个任务单独完成所需的时间 Ti 及其费用系数 Ci。

**输出格式**

输出一个整数，表示最小总费用。

**数据范围**

1 ≤ N ≤ 3 × 10 ^ 5，  
0 ≤ S，Ci ≤ 512，  
−512 ≤ Ti ≤ 512

**输入样例：**

5 1  
1 3  
3 2  
4 3  
2 3  
1 4

**输出样例：**

153  
来源：[https://www.acwing.com/problem/content/304/][https_www.acwing.com_problem_content_304]

**2. 思路分析：**

这道题目其实是[301题][301]的扩展，这里每一个点的斜率并一定是递增的，所以我们在查找的时候不能够直接将队列中的点删掉，这里我们可以使用二分找出第一个大于当前斜率s + t\[i\]的点，找到这个点f\[j\]来更新当前的f\[i\]，接下来的过程与301题的单调队列维护所有点的斜率都是单调递增的过程是一样的。

**3. 代码如下：**

if __name__ == "__main__":
        n, s = map(int, input().split())
        t, c = [0], [0]
        for i in range(1, n + 1):
            a, b = map(int, input().split())
            t.append(t[i - 1] + a)
            c.append(c[i - 1] + b)
        f = [0] * (n + 1)
        q = [0] * (n + 1)
        hh, tt = 0, 0
        # 而对于每一个f[i]斜率不是递增的则需要使用二分找到第一个大于当前斜率的f[j], 用找到的f[j]来更新当前的f[i], 那么得到的f[i]的花费就是最小的
        for i in range(1, n + 1):
            l, r = 0, tt
            # 二分的过程, 队列中找到第一个斜率大于当前直线斜率的点
            while l < r:
                mid = l + r >> 1
                if f[q[mid + 1]] - f[q[mid]] > (t[i] + s) * (c[q[mid + 1]] - c[q[mid]]): r = mid
                else: l = mid + 1
            j = q[r]
            f[i] = f[j] - (t[i] + s) * c[j] + t[i] * c[i] + s * c[n]
            # 单调队列过程, 单调队列维护的其实是所有斜率都是递增的f[j]
            while hh < tt and (f[q[tt]] - f[q[tt - 1]]) * (c[i] - c[q[tt - 1]]) >= (f[i] - f[q[tt - 1]]) * (c[q[tt]] - c[q[tt - 1]]): tt -= 1
            tt += 1
            q[tt] = i
        print(f[n])

[https_www.acwing.com_problem_content_304]: https://www.acwing.com/problem/content/304/
[301]: https://blog.csdn.net/qq_39445165/article/details/120688802