自动搬运

查看原文

来自洛谷，原作者为

	Tairitempest 今天TRTP吃什么？

搬运于2025-08-24 23:12:37，当前版本为作者最后更新于2025-04-11 13:08:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

[OOI 2025] Best Runner

跑步的跑道数最多的人跑的肯定是长度相对较短的跑道，因此最优策略要么跑的跑道没有重复，要么会最终在一条跑道上跑到结束。显然对于最优答案的位置，其可能的运动员一定是在其两侧距离最近的运动员.

如果从更远的地方跑过来，那么只可能有两种情况：路上的跑道都比最终所在位置的跑道更长，和路上存在更短的跑道。对于前者，因为路上的跑道长度更长，其一定不优；对于后者，因为中间存在更短的跑道，因此选择更短的跑道跑到结束一定更优。

用计算前后缀的方法处理出每个跑道左右两侧距离它最近的两个运动员即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,T,a[300010],b[300010],s[300010],ans=-1e18;
ll l[300010],r[300010];
ll cnt(ll f,ll t){
    if(t==f) return T/a[t];
    if(t>f) return (t-f)+(T-s[t-1]+s[f-1])/a[t];
    else return (f-t)+(T-s[f]+s[t])/a[t];
}
ll go(ll f,ll t){
    if(t>f) return (s[t-1]-s[f-1]);
    else return (s[f]-s[t]);
}
int main(){
    cin>>n>>m>>T;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=m;i++) cin>>b[i];
    for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];
    for(int i=1;i<=m;i++) l[b[i]]=r[b[i]]=b[i];
    for(int i=1;i<=n;i++) if(!l[i]) l[i]=l[i-1];
    for(int i=n;i>=1;i--) if(!r[i]) r[i]=r[i+1];
    for(int i=1;i<=n;i++){
        if(l[i]&&go(l[i],i)<=T) ans=max(ans,cnt(l[i],i));
        if(r[i]&&go(r[i],i)<=T) ans=max(ans,cnt(r[i],i));
    }
    cout<<ans<<endl;
    return 0;
}