题解

这是一道贪心 + 预处理前后最近起点 + 二分/公式计算的经典题，数据范围 $n \le 3\times10^5$，要求 $O(n)$ 或 $O(n\log n)$ 算法。

一、题目翻译与核心规则

题意

体育场有 $n$ 条跑道，第 $i$ 条跑道长度为 $a_i$（跑完需要 $a_i$ 秒）。 有 $m$ 个运动员，第 $i$ 个运动员从跑道 $b_i$ 的起点出发。

所有运动员训练 $T$ 秒，规则如下：

1. 运动员在跑道 $i$ 起点，跑完这条跑道耗时 $a_i$ 秒（算完成 1 圈）；
2. 跑完后瞬间移动，可以选择：
   • 回到当前跑道 $i$ 起点；
   • 移动到相邻跑道 $i-1$ 或 $i+1$ 起点；
3. 总时间不超过 $T$ 秒，求所有运动员能跑完的最大完整圈数。

关键结论（贪心核心）

要跑最多圈，最优策略一定是：

1. 从起点出发，单向移动到某一条跑道 $x$（只往左/只往右）；
2. 到达 $x$ 后，一直在 $x$ 反复跑圈，不再移动。 原因：移动不耗时，反复跑同一条跑道效率最高。

---

二、核心公式推导

设：

• 运动员从起点 $s$ 出发，走到目标跑道 $x$；
• 移动路径的总耗时：$\mathrm{cost}(s,x)$（只跑沿途跑道各一次，耗时为路径和）；
• 剩余时间：$T - \mathrm{cost}(s,x)$；
• 目标跑道 $x$ 每圈耗时 $a_x$，可跑圈数：$\left\lfloor \dfrac{T - \mathrm{cost}(s,x)}{a_x} \right\rfloor$；
• 总圈数 = 沿途跑道数（移动时跑的） + 反复跑圈数。

---

三、标程核心思路

1. 预处理前缀和

$s[i] = \sum_{j=1}^i a[j]$ 作用：$O(1)$ 计算任意区间 $[l,r]$ 的耗时和。

2. 预处理左右最近起点（最关键）

• $l[i]$：位置 $i$ 左边最近的运动员起点（包含自己）；
• $r[i]$：位置 $i$ 右边最近的运动员起点（包含自己）；

这样每个位置 $i$，只需要计算两个起点：

• 左边最近起点 $l[i]$ 到 $i$；
• 右边最近起点 $r[i]$ 到 $i$。

3. 遍历所有位置计算最大圈数

对每个跑道 $i$：

1. 计算从 $l[i]$ 走到 $i$ 的耗时；
2. 若耗时 $\le T$，计算总圈数；
3. 同理计算 $r[i]$ 走到 $i$；
4. 维护全局最大值。

---

四、标程函数详解

1. go(f, t)：计算从起点 $f$ 到目标 $t$ 的移动耗时

ll go(ll f,ll t){
    if(t>f) return s[t-1]-s[f-1];  // 向右走：跑 f ~ t-1 各一次
    else return s[f]-s[t];        // 向左走：跑 t+1 ~ f 各一次
}

• 向右 $f\to t$：耗时 = $a_f+a_{f+1}+...+a_{t-1}$
• 向左 $f\to t$：耗时 = $a_{t+1}+a_{t+2}+...+a_f$

2. cnt(f, t)：计算从 $f$ 出发到 $t$ 的总圈数

ll cnt(ll f,ll t){
    if(t==f) return T/a[t];                      // 不移动，直接跑
    if(t>f) return (t-f)+(T-go(f,t))/a[t];       // 向右：步数+剩余圈数
    else return (f-t)+(T-go(f,t))/a[t];          // 向左：步数+剩余圈数
}

• $(t-f)$：移动时跑的圈数；
• $(T-go(f,t))/a[t]$：剩余时间反复跑的圈数。

---

五、完整算法流程

1. 输入：$n, m, T$，数组 $a$，起点数组 $b$；
2. 前缀和：$s[i] = s[i-1]+a[i]$；
3. 预处理 $l$ 数组：从左到右，记录最近起点；
4. 预处理 $r$ 数组：从右到左，记录最近起点；
5. 遍历每个位置 $i$：
   • 用 $l[i]$ 计算到 $i$ 的圈数；
   • 用 $r[i]$ 计算到 $i$ 的圈数；
   • 更新答案最大值；
6. 输出答案。

---

六、样例演算（第一个样例）

输入： $n=5,\ m=3,\ T=10$ $a = [4,5,2,7,1]$ 起点：$1,2,4$

预处理

$l = [0,1,2,2,4,4]$ $r = [0,1,2,4,4,0]$

计算位置 5

• 最近起点 $r[5]=4$；
• $go(4,5) = a[4] =7$；
• 剩余时间 $10-7=3$；
• 反复跑 $a[5]=1$，圈数 $3/1=3$；
• 总圈数 $1+3=4$ → 最大值。

输出：$\boldsymbol{4}$。

---

七、复杂度分析

• 前缀和：$O(n)$
• 预处理 $l/r$ 数组：$O(n)$
• 遍历计算：$O(n)$ 总复杂度：$\boldsymbol{O(n)}$，完美通过 $3\times10^5$ 数据。

---

八、标程代码注释版

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN = 3e5 + 10;

ll n, m, T;
ll a[MAXN], b[MAXN], s[MAXN];   // s：前缀和
ll l[MAXN], r[MAXN];            // l[i]：左最近起点，r[i]：右最近起点
ll ans = -1e18;

// 计算从 f 到 t 的总圈数
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];
}

// 计算从 f 到 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() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    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;
}

---

总结

1. 贪心策略：先移动到最优跑道，再反复刷圈；
2. 优化核心：用 $l/r$ 数组跳过无效起点，$O(1)$ 查询最近起点；
3. 公式：总圈数 = 移动步数 + 剩余时间//单圈耗时；
4. 复杂度：$O(n)$，通过全部测试点。