当前位置 : 主页 > 网页制作 > HTTP/TCP >

CH301 任务安排2 题解报告

来源:互联网 收集:自由互联 发布时间:2021-06-16
题目传送门 【题目大意】 题意同 任务安排1 ,数据范围变为$1\le N\le3*10^5,1\le S,T_i,C_i\le512$ 【思路分析】 我们对任务安排1的解法稍作优化 设$st,sc$分别为$T,C$数组的前缀和,转移方程转

题目传送门

【题目大意】

题意同任务安排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 }
代码戳这里
网友评论