题解：P12078 [OOI 2025] Best Runner

Tairitempest · 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;
}