301 任务安排2（斜率优化）

深碍√TFBOYSˉ_ 2022-09-15 06:08 151阅读 0赞

**1. 问题描述：**

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

**输入格式**

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

**输出格式**

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

**数据范围**

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

**输入样例：**

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

**输出样例：**

153

来源：[https://www.acwing.com/problem/content/description/303/][https_www.acwing.com_problem_content_description_303]

**2. 思路分析：**

这道题目与[300题任务安排I][300_I]题除了数据规模之外其余的都是一模一样的，属于**斜率优化**的题目，如果使用300题中暴力枚举的思路那么肯定是超时的，所以需要使用斜率优化来解决，一般斜率优化的题目涉及到的状态转移方程都是很复杂的，我们需要对方程变形进一步分析得到优化的结果。300题的状态转移方程为：f\[i\] = f\[j\] - (t\[i\] + s) \* c\[j\] + t\[i\] \* c\[i\] + s \*c\[n\]，0 <= j <= i - 1，对其变形可以得到：f\[j\] = f\[i\] + (t\[i\] + s) \* c\[j\] - t\[i\] \* c\[i\] - s \*c\[n\]，0 <= j <= i - 1，对于每一个i来说对应的参数都是固定的，所以唯一的变量就是j，我们可以将f\[j\]看成是y，c\[j\]看成是x，(t\[i\] + s) 看成是斜率k，f\[i\] - t\[i\] \* c\[i\] - s \*c\[n\]看成是截距b，那么状态转移方程可以看成是关于x和y的直线方程，我们的目标是使得f\[i\]最小，所以当第i个点的斜率固定的时候，而(c\[j\]，f\[j\]）可以看成是直线上的点，我们需要使得f\[i\]最小那么应该使得截距b越小，并且可以发现只有外围的点才可以作为答案输出，因为在外围内的点的截距更大不可能作为答案输出，所以我们在维护f\[j\]的时候其实是维护外围的点，也即凸包下边界的点，我们需要在维护的凸包中找到截距最小的点，相当于是在单调队列中找到第一个大于某个数的点，由于这道题目的斜率和横坐标都是单调递增的，所以我们可以使用一个单调队列来维护，在查询的时候将队头中所有斜率小于等于当前直线斜率的点删掉，并且在插入的时候将队尾所有不在凸包的点全部删掉：① (f2 - f1) / (c2 - c1) <= t\[i\] + s ② (ftt - ftt-1) / (ctt - ctt-1) >= (fi - ftt-1) / (ci - ctt-1)， 单调队列维护的是当前最小的f\[j\]。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_19_color_FFFFFF_t_70_g_se_x_16][]

**3. 代码如下：**

if __name__ == "__main__":
        n = int(input())
        s = int(input())
        t, c = [0], [0]
        for i in range(n):
            a, b = map(int, input().split())
            # 预处理前缀和
            t.append(t[-1] + a)
            c.append(c[-1] + b)
        f = [0] * (n + 1)
        # 一开始的时候队列有一个元素f[0]
        q = [0] * (n + 1)
        hh, tt = 0, 0
        for i in range(1, n + 1):
            while hh < tt and f[q[hh + 1]] - f[q[hh]] <= (c[q[hh + 1]] - c[q[hh]]) * (t[i] + s): hh += 1
            j = q[hh]
            f[i] = f[j] - (t[i] + s) * c[j] + t[i] * c[i] + s * c[n]
            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_description_303]: https://www.acwing.com/problem/content/description/303/
[300_I]: https://blog.csdn.net/qq_39445165/article/details/120678505
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_19_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/684852cdb04a49efb7bd14f2ddba923f.png