当前位置：首页 > news >正文

信息学奥赛一本通 ybt 1608：【例 3】任务安排 3 | 洛谷 P5785 [SDOI2012] 任务安排

news 来源：原创 2025/5/19 14:43:31

【题目链接】

ybt 1608：【例 3】任务安排 3
洛谷 P5785 [SDOI2012] 任务安排

【题目考点】

1. 动态规划：斜率优化动规

2. 单调队列

3. 二分答案

【解题思路】

与本题题面相同但问题规模不同的题目：
信息学奥赛一本通 1607：【例 2】任务安排 2 | 洛谷 P10979 任务安排 2
本题相比上题只有 $t_i$ 的数值范围从 $t_i\le 2^8$ ，变为 $|t_i| \le 2^8$ ，也就是 $-2^8 \le t_i \le 2^8$
斜率优化相关内容已在上题中有详细解释，本题不再赘述。请先看上题题解，而后再看本题题解。

本题中 $t_i$ 可能是负数，求出的前缀和 $T_i$ 也可能是负数。
随着 $i$ 的增大 $T_i$ 不再是单调递增的，直线斜率 $K=T_i+s$ 随着 $i$ 的增大也不再是单调递增的。因此上题题解中8. 决策点队头出队中所述的方法不再适用。本题需要维护所有下凸壳上的决策点。

已知决策点比较条件为：
在 $C_{j_1}<C_{j_2}$ 的前提下：

如果 $k(j_1,j_2) > K$ ，那么决策点 $j_1$ 优于 $j_2$
如果 $k(j_1,j_2) < K$ ，那么决策点 $j_2$ 优于 $j_1$

决策点集的下凸壳上的所有决策点按 $C_j$ 从小到大记为 $q_l,q_{l+1},...,q_r$ ，保存在一个单调队列中，相邻点连线的斜率是单调递增的：
$k(q_l,q_{l+1})<k(q_{l+1},q_{l+2})<...<k(q_{r−1},q_r)$

那么从 $q_l$ 看到 $q_r$ ，找到第一个满足 $k(q_m,q_{m+1})≥K$ 的决策点 $q_m$ ， $q_m$ 就是最优决策点。
如果没有满足条件的点，则选择队列最后一个点 $q_r$ 为最优决策点。
该过程可以通过二分答案完成

答案变量： $q$ 数组下标m，初始范围 $[l, r]$
最值：求最小值
满足条件： $k(q_m,q_{m+1})≥K$

如果存在满足条件的决策点，返回二分答案的结果m，取最优决策点 $q_m$ 。
如果不存在满足条件的决策点，二分答案的结果就是初始范围的右端点r，此时返回r，取到的最优决策点是 $q_r$

条件 $k(q_m,q_{m+1})≥K$ 经过十字相乘后变为 $(dp_{q_{m+1}}-dp_{q_m})\ge K (C_{q_{m+1}}-C_{q_m})$
算法时间复杂度为 $O (n l o g n)$

在这里插入图片描述
图示：
一种可能的情况：
i为1时，直线斜率为 $K_1$ ，第一个满足条件的是 $k(q_3,q_4)\ge K_1$ ，最优决策点为 $q_3$
i为2时，直线斜率为 $K_2$ ，第一个满足条件的是 $k(q_2,q_3)\ge K_2$ ，最优决策点为 $q_2$
i为3时，直线斜率为 $K_3$ ，没有满足条件的点，最优决策点为最后一个点 $q_5$

【题解代码】

解法1：斜率优化动规，二分查找最优决策点 $O (n l o g n)$

#include<bits/stdc++.h>
using namespace std;
#define N 300005
long long n, s, t[N], c[N], T[N], C[N], dp[N];//dp[i]:前i个任务的所有子段划分方案中，执行任务的费用 加上当前方案下每批任务的启动时间对后续任务产生的费用加和 最小的划分方案的费用
int q[N];
int binarySearch(int l, int r, int k)//通过二分查找找到第一个满足k(q[m], q[m+1])>=k的m，返回m。找不到满足条件的点，会返回r。 
{while(l < r){int m = (l+r)/2;if((dp[q[m+1]]-dp[q[m]]) >= k*(C[q[m+1]]-C[q[m]]))r = m;elsel = m+1; } return l; 
}
int main()
{int l = 1, r = 0;//单调队列队头队尾下标 cin >> n >> s;for(int i = 1; i <= n; ++i){cin >> t[i] >> c[i];T[i] = T[i-1]+t[i];C[i] = C[i-1]+c[i];}q[++r] = 0;//加入(C[0],dp[0])点 for(int i = 1; i <= n; ++i){int b = binarySearch(l, r, T[i]+s);dp[i] = dp[q[b]]-(T[i]+s)*C[q[b]]+T[i]*C[i]+s*C[n];while(l < r && (dp[i]-dp[q[r]])*(C[q[r]]-C[q[r-1]]) <= (C[i]-C[q[r]])*(dp[q[r]]-dp[q[r-1]]))--r;q[++r] = i;}cout << dp[n];return 0;
}