CH301 任务安排2 题解报告

题目传送门

【题目大意】

题意同任务安排1，数据范围变为$1\le N\le3*10^5,1\le S,T_i,C_i\le512$

【思路分析】

我们对任务安排1的解法稍作优化

设$st,sc$分别为$T,C$数组的前缀和，转移方程转化为$f[i]=min\{f[j]-(st[i]+S)*sc[j]\}(0\le j<i)+st[i]*sc[i]+S*sc[n]$

我们去掉$min$函数，然后将关于$j$的值$f[j],sc[j]$看作变量，其余部分看作常量，则$f[j]=(st[i]+S)*sc[j]+f[i]-st[i]*sc[i]-S*sc[n]$

然后我们以$sc[j]$为横坐标，$f[j]$为纵坐标建立平面直角坐标系，那么这就是一条斜率为$st[i]+S$，在$y$轴上截距为$f[i]-st[i]*sc[i]-S*sc[n]$的直线。相当于，候选集合是坐标系中的一个点集，每个决策$j$都对应着坐标系中的一个点$(sc[j],f[j])$。直线的斜率是固定的，截距越小，则$f[i]$越小。

为了及时排除无用决策，我们维护一个“连接相邻两点的线段斜率单调递增”的“下凸壳”。对于一条斜率为$k$的直线，若某个顶点左侧线段斜率$<k$，右侧线段斜率$>k$，则该顶点即为最优决策。

具体地，我们可以利用单调队列来维护这个下凸壳。单调队列$q$中保存若干个决策变量，对应凸壳上的顶点，且满足横坐标递增，连接相邻两点的线段斜率也单调递增。

对于每个状态变量$i$，我们进行如下操作：

$1.$检查队头的两个决策变量$q[l],q[l+1]$，若斜率$\frac{f[q[l+1]]-f[q[l]]}{sc[q[l+1]]-sc[q[l]]}\le S+st[i]$，则把$q[l]$出队，重复该操作直到队头元素不满足条件为止

$2.$此时的队头$q[l]$即为最优决策，计算出$f[i]$

$3.$检查队尾元素$q[r-1],q[r]$和$i$是否满足斜率单调递增，若不满足则将$q[r]$出队，重复操作直到队尾元素满足斜率单调递增，将$i$插入进队尾

整个算法的时间复杂度为$O(N)$

【代码实现】

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 #include<queue>
 7 #define g() getchar()
 8 #define rg register
 9 #define go(i,a,b) for(rg int i=a;i<=b;i++)
10 #define back(i,a,b) for(rg int i=a;i>=b;i--)
11 #define db double
12 #define ll long long
13 #define il inline
14 #define pf printf
15 #define mem(a,b) memset(a,b,sizeof(a))
16 using namespace std;
17 int fr(){
18     int w=0,q=1;
19     char ch=g();
20     while(ch<‘0‘||ch>‘9‘){
21         if(ch==‘-‘) q=-1;
22         ch=g();
23     }
24     while(ch>=‘0‘&&ch<=‘9‘) w=(w<<1)+(w<<3)+ch-‘0‘,ch=g();
25     return w*q;
26 }
27 const int N=3e5+2;
28 int n,s,q[N],l=1,r=1;
29 ll f[N],st[N],sc[N],as;
30 int main(){
31     //freopen("","r",stdin);
32     //freopen("","w",stdout);
33     n=fr();s=fr();
34     go(i,1,n)st[i]=st[i-1]+fr(),sc[i]=sc[i-1]+fr();
35     mem(f,0x3f);f[0]=0;
36     q[1]=0;as=s*sc[n];
37     go(i,1,n){
38         rg ll k=s+st[i];
39         while(l<r&&f[q[l+1]]-f[q[l]]<=k*(sc[q[l+1]]-sc[q[l]]))l++;
40         f[i]=f[q[l]]-k*sc[q[l]]+st[i]*sc[i]+as;
41         while(l<r&&(f[q[r]]-f[q[r-1]])*(sc[i]-sc[q[r]])>=(f[i]-f[q[r]])*(sc[q[r]]-sc[q[r-1]]))r--;
42         q[++r]=i;
43     }
44     pf("%lld\n",f[n]);
45     return 0;
46 }