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

【题目链接】

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})\ge K$的决策点$q_m$，$q_m$就是最优决策点。
如果没有满足条件的点，则选择队列最后一个点$q_r$为最优决策点。
该过程可以通过二分答案完成

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

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

条件$k(q_m,q_{m+1})\ge K$经过十字相乘后变为$(d{p}_{q_{m+1}}-d{p}_{q_m})\ge K(C_{q_{m+1}}-C_{q_m})$
算法时间复杂度为$O(nlogn)$

图示：
一种可能的情况：
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(nlogn)$

#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;
		else
			l = 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;
}