题解 P12078 [OOI 2025] Best Runner

Part 1 理解题意

这道题的意思是每一个跑者跑完当前跑道后可以去跑相邻的跑道或者当前的跑道，问在一定时间内完整跑完跑道次数最多的跑者最多能完整跑完多少条跑道。

Part 2 分析思路

跑短的跑道显然能跑更多次，所以最优策略就是跑过的所有跑道上除了最短的都只跑一次，但是每个运动员去左右两边找短的跑道肯定会超时，所以让跑道去找两边最近的两个运动员，再计算答案。

可能有人想问，假如当前正在计算的跑道够短，难道更远的地方的运动员不会过来吗？其实更远的地方跑过来，跑的跑道条数一定大于两边的运动员，因为他们在路上跑过的跑道更多，而题目中只求一个最大值，所以无需考虑更远的运动员。

但是还会超时，所以考虑前缀和后缀优化，具体看代码注释。

Part 3 参考代码

CPP

#include<bits/stdc++.h>
using namespace std;
long long t;
long long a[300010],b[300010];
long long s[300010];//a数组的前缀和
long long l[300010];//一条跑道左边最近的运动员
long long r[300010];//一条右边最近的运动员
long long go(long long x,long long y){
    //从x开始跑到y，路程上的所有跑道的长度和（不含y）。
    if (y > x) {
        return s[y]-s[x];//前缀和快速计算
    } else {
        return s[x-1]-s[y-1];
    }
}
long long f(long long x,long long y) {
    //计算从y跑到x再在x上跑到时间用完的跑道条数
    long long sum = 0;
    sum += go(y,x);//计算来x的路程上的长度和
    long long ans = 0;
    ans += abs(y-x);//来x的路程上跑的跑道条数
    ans += (t-sum)/a[y];//计算还能在x上跑几次
    return ans;
}
int main() {
    //输入
    int n,m;
    cin >> n >> m >> t;
    for (int i=1;i<=n;i++) {
        cin >> a[i];
    }
    for (int i=1;i<=m;i++) {
        cin >> b[i];
    }
    //计算a数组前缀和
    for (int i=1;i<=n;i++) {
        s[i] = s[i-1]+a[i];
    }
    //计算每条跑道左右两边最近的运动员
    for (int i=1;i<=m;i++) {
        l[b[i]] = b[i];//当前跑道有运动员
        r[b[i]] = b[i];
    }
    //类似前缀和后缀思想求左右两边最近的运动员
    for (int i=1;i<=n;i++) {
        if (l[i] == 0) {
            l[i] = l[i-1];
        }
    }
    for (int i=n;i>=1;i--) {
        if (r[i] == 0) {
            r[i] = r[i+1];
        }
    }
    //计算答案
    long long ans = -9e18;
    for (int i=1;i<=n;i++) {
        //左边有运动员且时间够跑过来
        if (l[i] > 0 && go(i,l[i]) <= t) {
            ans = max(ans,f(l[i],i));//更新答案
        }
        //右边有运动员且时间够跑过来
        if (r[i] > 0 && go(i,r[i]) <= t) {
            ans = max(ans,f(r[i],i));//更新答案
        }
    }
    //输出答案
    cout << ans << endl;
    return 0;
}

有问题发在评论里，我很乐意回答哦~

题解：P12078 [OOI 2025] Best Runner

文章操作