网站建设公司专业开发北京网站_手术直播平台_建立自己的网站平台_青岛网站优化公司哪家好

$\text{[Problem Discription]}$

Jill 喜欢在大学里取得好成绩，因此她从来没有错过任何的 ddl。不过，她也特别喜欢追剧并与她最好的朋友 Johnny 讨论。不幸的是，如今她必须在两件事之间做出抉择。

Jill 需要完成 $n$ 项作业，每项作业需要 $a_i$ 时间，且不能晚于 $d_i$ 提交。同时，有 $m$ 部剧也等着 Jill 去追。第 $j$ 部剧的长度是 $l_j$ 分钟。Jill 可以以任意的顺序完成任务，但是必须以从 $1$ 到 $m$ 的顺序追剧。不能同时写作业和追剧，也不能同时写两项作业或看两部剧。

Johnny 和 Jill 商议在第 $t_k$ 分钟讨论她俩所追的剧。不过她们还没确定 $t_k$ 的具体值。对于每个可能的 $t_k$，计算 Jill 在按时完成所有作业的前提下最多能追几部剧。

我们假设 Jill 和 Johnny 的讨论并不会占用 Jill 大量的时间。即她俩的讨论可以发生在 Jill 正在处理她的任何一项作业时。

Translated by luogu user HPXXZYY(me).

$\text{[Analysis]}$

首先容易想到的是，最优方案下作业的排序一定是按照 ddl 从小到大的顺序。

简要证明：使用反证法。如果最优方案下存在一个 ddl 靠后的作业 $u$ 排在了 ddl 靠前的作业 $v$ 前面。既然这样的排序并没有使得 $v$ 超时，那么我们交换 $u,v$ 的顺序，$v$ 写完的时间更加靠前，而 $u$ 写完的时间早于等于 $d_v$，也一定早于 $d_u$。因此交换 $u,v$ 并不会使得方案不合法。

贪心。如果在某项 ddl 前有足够的时间把一部剧追完，就追。但是这样是有后效性的，很可能不看这部剧后面的 ddl 不会超时，但是看了就会。

所以需要有反悔机制。如果扫描到后面的某个 ddl 发现会超时了，就撤回一个乃至多个追剧的操作，直到不超时为止。

可以记录下每部剧最早可能在哪个时间被刷完，然后离线回答询问。这部分用二分就可以解决。

这样就得到了第一份代码（先说明，这份代码不能 AC。如果您的目标就是直奔 AC，可以跳过这份代码）。

const ll inf=1e18;
const int N=2e5+100;int n,m,q,T,a[N],L[N],order[N];
ll d[N],t[N],rec[N];bool cmp(int u,int v){return d[u]<d[v];
}void calc_time(){for(int i=1;i<=m;i++)rec[i]=inf;ll pre=0;int r=0;while (r<m&&pre<=d[order[1]]){++r;pre+=L[r];rec[r]=pre;if (r==m) break;} for(int i=1;i<=n;i++){pre+=a[order[i]];while (d[order[i]]<pre){pre-=L[r];rec[r--]=inf;}//无法完成 ddl while (r<m&&pre<=d[order[i+1]]){++r;pre+=L[r];rec[r]=pre;} }while (r<m){++r;pre+=L[r];rec[r]=pre;}
}//rec[i] 表示第 i 部剧最早在 rec[i] 的时间被刷完int Bineary_Search(ll key){int l=1,r=m,ans=0;while (l<=r){int mid=(l+r)>>1;if (key>=rec[mid]){ans=mid;l=mid+1;}else r=mid-1;}return ans;
}void Read_data(){n=read();m=read();q=read();for(int i=1;i<=n;i++) a[i]=read();for(int i=1;i<=n;i++) d[i]=read();for(int i=1;i<=m;i++) L[i]=read();for(int i=1;i<=n;i++) order[i]=i;sort(order+1,order+n+1,cmp);d[n+1]=inf;
}int put_answer(){for(int i=1;i<=q;i++){ll t=read();int tmp=Bineary_Search(t);printf("%d ",tmp);}return printf("\n");
}int HPXXZYY(){Read_data();calc_time();return put_answer();
}int main(){T=read();while (T--) HPXXZYY();return 0;
}

这份代码的评测结果是 TLE on test $25$。可以断定的是，这份代码的思路肯定是没有问题的。只是我们需要给这份代码加速。

那就先得想哪里会导致 TLE。很显然，在撤销“追剧”操作时，极端情况下，可能上一个 ddl 时 $r$ 扫描到最后一部剧，而下一个 ddl 又把 $r$ 撤回了 $1$。最坏情况下时间复杂度是 $O(nm)$。

考虑使用离线加速。简单的说，如果后面一项 ddl 要求最多只能刷 $x$ 部剧，那么前面的 ddl 最多也只能刷 $x$ 部剧，刷多了也得被撤回来。

用二分法可以求出不计后效性的情况下每个 ddl 前最多可以刷多少部剧，设为 ${\text{tmp}}_i$。根据上面的分析，最优方案下每个 ddl 前最多可以刷的剧的数量就是：

$$\underset{j=i}{\overset{n}{\min }}{\text{tmp}}_j$$

然后就可以做到稳定 $O(n+m)$ 的扫描。

最终单组数据的总时间复杂度为 $O(n\log m+q\log m)$。

$\text{Final Code}$

const ll inf=1e18;
const int N=2e5+100;int n,m,q,T,a[N],L[N],order[N];
ll d[N],t[N],rec[N],pre[N],cost[N];bool cmp(int u,int v){return d[u]<d[v];
}void make_preparation(){for(int i=1;i<=n;i++) order[i]=i;sort(order+1,order+n+1,cmp);//间接排序for(int i=1;i<=n;i++)pre[i]=pre[i-1]+a[order[i]];for(int i=1;i<=m;i++)cost[i]=cost[i-1]+L[i];
}int Bineary_Search(ll key){int l=1,r=m,ans=0;while (l<=r){int mid=(l+r)>>1;if (cost[mid]<=key){ans=mid;l=mid+1;}else r=mid-1;}return ans;
}//注意，Bineary_Search 这个函数和上一份代码的作用不一样int tmp[N];
void calc_time(){for(int i=1;i<=m;i++) rec[i]=inf;for(int i=1;i<=n;i++)tmp[i]=Bineary_Search(d[order[i]]-pre[i]);//最多可以看几部剧 tmp[n+1]=m+1;for(int i=n;i>=1;i--)tmp[i]=min(tmp[i+1],tmp[i]);//考虑后效性ll Time=0;int r=0; for(int i=1;i<=n;i++){while (r<tmp[i]){++r;Time+=L[r];rec[r]=Time;}Time+=a[order[i]];}while (r<m){++r;Time+=L[r];rec[r]=Time;}
}int Get_Answer(ll key){int l=1,r=m,ans=0;while (l<=r){int mid=(l+r)>>1;if (key>=rec[mid]){ans=mid;l=mid+1;}else r=mid-1;}return ans;
}void Read_data(){n=read();m=read();q=read();for(int i=1;i<=n;i++) a[i]=read();for(int i=1;i<=n;i++) d[i]=read();for(int i=1;i<=m;i++) L[i]=read();
}int put_answer(){for(int i=1;i<=q;i++){ll t=read();int tmp=Get_Answer(t);printf("%d ",tmp);}return printf("\n");
}void clear_data(){for(int i=1;i<=n;i++)pre[i]=tmp[i]=0;for(int i=1;i<=m;i++)cost[i]=0;
}int HPXXZYY(){Read_data();clear_data();make_preparation();calc_time();return put_answer();
}int main(){T=read();while (T--) HPXXZYY();return 0;
}//很喜欢这种主程序啥也不干的写法