形式化题目

环形公路上均匀分布 $N$ 座仓库，编号 $1\sim N$。编号 $i$ 与 $j$ 的仓库之间的环上最短距离为

仓库 $i$ 的库存量为 $A_i$，在 $i$ 与 $j$ 之间运货的代价为

求

输入样例：

1
25
1 8 6 2 5

输出样例：

115

样例里的环形公路如下：节点内标出库存量，边上的 $1$ 是相邻编号仓库之间的距离。 把边上权值沿环累加就得到 $dist$。

graph LR
    W1["仓库1<br/>A=1"]
    W2["仓库2<br/>A=8"]
    W3["仓库3<br/>A=6"]
    W4["仓库4<br/>A=2"]
    W5["仓库5<br/>A=5"]
    W1 ---|1| W2
    W2 ---|1| W3
    W3 ---|1| W4
    W4 ---|1| W5
    W5 ---|1| W1

读图时注意 $dist$ 是环上两个方向的较小值，把边上的 $1$ 累加就得到距离： 仓库 $5$ 与仓库 $1$ 相邻，距离为 $1$；仓库 $5$ 到仓库 $2$ 的两个方向分别是 $2$（经仓库 $1$） 和 $3$（经仓库 $4,3$），取较小的 $2$。 按公式逐一算：选择仓库 $2$ 与仓库 $3$ 得 $8+6+1=15$， 选择仓库 $5$ 与仓库 $2$ 得 $5+8+2=15$，两者并列最优。

正解

思路

朴素做法与瓶颈。 数据范围是 $1\leqslant N\leqslant 10^6$、$1\leqslant A_i\leqslant 10^7$。 枚举所有 $i<j$，把环上较短路代入求值（这里 A 是 0 起始下标的库存数组，长度 n）：

1best = max(A[i] + A[j] + min(j-i, n-(j-i)) for i in range(n) for j in range(i+1, n))

这是 $O(N^2)$，$N=10^6$ 时约 $5\times 10^{11}$ 次运算，必须把“每个右端点都扫一遍所有左端点” 压到摊还 $O(1)$。

第一步：断环成链，把环形距离变成下标差。

两个方向的距离之和恒为 $N$，所以较短路必然不超过 $K=\lfloor N/2\rfloor$。于是把数组复制出前 $K$ 项接在后面：

那么，这样做会不会落下某一对仓库？设一对仓库编号 $u<v$，取较短路长度 $d=dist(u,v)\leqslant K$。 若 $v-u=d\leqslant K$，则下标对 $(u,v)$ 本身就在链的前 $N$ 项里； 若 $v-u>K$，则 $v-u\geqslant K+1$，较短路是从 $v$ 绕回 $u$、长度 $d=N-(v-u)$， 且由 $u\leqslant v-(K+1)\leqslant N-K-1$ 得 $u\leqslant K$（因为 $K=\lfloor N/2\rfloor$ 推出 $N-K-1\leqslant K$）。 于是下标对 $(v,\;u+N)$ 落在链上（$u+N\leqslant N+K$），且 $(u+N)-v=N-(v-u)=d\leqslant K$。两种情形都被覆盖。

链上满足 $j-i\leqslant K$ 的下标 $(i,j)$，其下标差 $j-i$ 就等于这两座仓库的环上较短路距离 （因为 $j-i\leqslant K$ 意味着这个方向不比另一个方向 $N-(j-i)$ 远），所以每个下标对都是一对真实仓库的合法候选。 例如样例中仓库 $5$ 与仓库 $2$：

1
2
3
4
5N = 5   K = N // 2 = 2   链长 = N + K = 7

下标    1   2   3   4   5   6   7
库存    1   8   6   2   5   1   8
来源    A   A   A   A   A  复  复

下标 $5$ 到下标 $7$ 的距离是 $7-5=2$，正是仓库 $5$ 到仓库 $2$ 绕环的较短路距离。

要注意距离小于 $K$ 的仓库对会在链上出现两次（例如仓库 $1,2$ 对应下标 $1,2$ 和 $6,7$）， 距离恰为 $K$（$N$ 为偶数）时同样如此。幸好本题只求最大值、不计数： 重复出现的下标对算出的就是同一个代价，既不会把答案抬高，也不会漏掉任何一对。 这是断环成链能直接用在本题的关键前提。

第二步：把 $j-i$ 拆开，让左右端点各管一半。

$f$ 只和左端点有关，$g$ 只和右端点有关，于是问题变成

第三步：滑动窗口最大值用单调队列。

右端点 $j$ 从小到大枚举，窗口 $[j-K,j-1]$ 的左右两端都单调右移，正是单调队列的场景。 队列存左端点下标，并维护 $f$ 从队首到队尾严格递减，这样队首就是窗口内 $f$ 最大者：

1. 新的左端点 $i=j-1$ 入队前，先弹出队尾所有 $f$ 值不大于 $f(i)$ 的下标——它们既更小、又更早过期，永远不可能再当选；
2. 再看队首是否已滑出窗口（下标 $<j-K$），是则弹出；
3. 此时队首就是窗口内最优左端点，算出候选值并更新答案。

样例的完整扫描轨迹。表里的下标都换算成 $1$ 起始编号，所以 $f(i)=B_i-i$、$g(j)=B_j+j$； “队列中的下标”按从队首到队尾排列，队首就是候选值的取值位置：

第 $3$ 行是本题答案的来源：扫到 $j=3$（$B_3=6$，仓库 $3$）时，窗口是下标 $1\sim2$， 但入队下标 $2$ 时发现它的 $f(2)=8-2=6$ 不小于下标 $1$ 的 $f(1)=1-1=0$，于是下标 $1$ 被弹出。 队首因此是下标 $2$（仓库 $2$），候选值 $f(2)+g(3)=6+(6+3)=15$，即 $8+6+1$。 第 $7$ 行给出了并列最优的另一对（仓库 $5$ 与仓库 $2$，代价 $5+8+2=15$），它只在下标 $7$ 这个复制出来的位置上才会出现， 这也说明了为什么要复制前 $K$ 项。

正确性要点。 每一步入队弹出的队尾元素既比新元素更早过期、值又不更大，因此删除它们不改变任何后续窗口的最优值； 被弹出的队首元素已不在窗口内。故循环过程中队首始终是当前窗口内 $f$ 的最大值， 每次得到的候选值都对应链上一对满足 $j-i\leqslant K$ 的下标，也就是一对真实仓库的合法代价， 取最大即得答案。

边界。 当 $N=1$ 时链长为 $1$，扫描循环一次都不执行；因为 $A_i\geqslant 1$，把 best 初始化成 $0$ 直接输出， 正好对应“找不到第二座仓库”。

正文与代码的对应关系是直接的：parse_chain() 完成第一步的断环成链， best_cost() 里的 weight = chain[i] - i 就是 $f(i)$，chain[j] + j 就是 $g(j)$， 两个 while 分别完成入队弹出与窗口过期，queue[0] 就是上表里的“队首”。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 11:30
 * update_at: 2026-10-10 11:30
 */
// 环形仓库配对：断环成链 + 单调队列，求 max(A[i] + A[j] + (j - i))。
#include <cstdio>
#include <vector>

typedef long long ll;

int main() {
    ll n;
    if (scanf("%lld", &n) != 1) return 0; // 空输入安全返回
    std::vector<ll> a(n);
    for (ll i = 0; i < n; i++) scanf("%lld", &a[i]);

    ll reach = n / 2; // 环上每一对仓库总有一个方向距离不超过 n // 2
    std::vector<ll> chain;
    for (ll i = 0; i < n; i++) chain.push_back(a[i]);
    for (ll i = 0; i < reach; i++) chain.push_back(a[i]); // 跨过编号 n 的那一对也落进同一条链

    std::vector<ll> q(chain.size() + 1); // 存左端点下标，权值 A[i] - i 从队首到队尾严格递减
    ll head = 0, tail = 0;
    ll best = 0; // A[i] >= 1，所以 0 是安全的初值

    for (ll j = 1; j < (ll)chain.size(); j++) {
        ll i = j - 1;
        ll weight = chain[i] - i;
        while (tail > head && chain[q[tail - 1]] - q[tail - 1] <= weight) {
            tail--; // 队尾更小又更早过期，不再可能当选
        }
        q[tail++] = i;
        while (q[head] < j - reach) head++; // 距离超过 reach 的左端点滑出窗口
        ll cost = chain[q[head]] - q[head] + chain[j] + j;
        if (cost > best) best = cost;
    }
    printf("%lld\n", best);
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 21:10
# update_at: 2026-10-01 21:10

import re
import sys
from array import array
from collections import deque

NUMBER_RE = re.compile(rb"\d+")  # 题面只出现非负整数，按数字串切分比 split 省一大半内存


def parse_chain() -> tuple[array, int]:
    """读入仓库数 n 与库存 A，返回“断环成链”后的库存序列以及窗口允许的最大下标差。"""
    buf = sys.stdin.buffer.read()
    values = array("i", (int(m.group()) for m in NUMBER_RE.finditer(buf)))
    del buf                                        # 原始字节只用于切分，尽早释放
    n = values[0]
    reach = n // 2                                 # 环上每一对仓库总有一个方向距离不超过 n // 2
    chain = values[1:n + 1] + values[1:1 + reach]  # 跨过编号 n 的那一对也落进同一条链
    del values
    return chain, reach


def best_cost(chain: array, reach: int) -> int:
    """求链上 max(A[i] + A[j] + (j - i))，只保留下标差 1 <= j - i <= reach 的配对。

    距离并进点权后，右端点 j 只需在滑动窗口 [j - reach, j - 1] 里问
    “谁的 A[i] - i 最大”，取窗口最大值正是单调队列的职责。
    """
    queue: deque[int] = deque()  # 存左端点下标，链上权值 A[i] - i 从队首到队尾严格递减
    best = 0                     # A[i] >= 1，所以 0 是安全的初值，n = 1 时直接输出它
    for j in range(1, len(chain)):
        i = j - 1                                     # j 左边最近的仓库，一定在窗口内
        weight = chain[i] - i                         # 该左端点的 f(i)
        while queue and chain[queue[-1]] - queue[-1] <= weight:
            queue.pop()                               # 队尾更小又更早过期，不再可能当选
        queue.append(i)
        while queue[0] < j - reach:                   # 距离超过 reach 的左端点滑出窗口
            queue.popleft()
        cost = chain[queue[0]] - queue[0] + chain[j] + j
        if cost > best:
            best = cost
    return best


def solve() -> None:
    chain, reach = parse_chain()  # n = 1 时链长为 1，扫描循环不执行，答案就是 best 的初值 0
    print(best_cost(chain, reach))


if __name__ == "__main__":
    solve()

复杂度

• 时间复杂度：$O(N)$。断环成链是 $O(N)$，单调队列扫描链长 $N+K=O(N)$， 且每个下标最多入队、出队各一次。
• 空间复杂度：$O(N)$。链 $B$ 用 array('i') 存放，占 $4(N+K)$ 字节；队列最多同时容纳 $K$ 个下标。

总结

这道题的核心是把“环形 + 距离”这两个麻烦逐个消掉：

1. 环 → 用 $dist\leqslant\lfloor N/2\rfloor$ 断环成链，把环形距离变成链上下标差；
2. 距离 → 把 $j-i$ 拆给左右端点，让 $f(i)=B_i-i$ 与 $g(j)=B_j+j$ 各自独立；
3. 取最大值 → 窗口两端单调右移，用单调队列把每个右端点的 $O(N)$ 降到摊还 $O(1)$。

只要题目求的是最大值而不是计数，第 1 步的重复枚举就完全无害——这是断环成链能直接用在本题的关键前提。 第 2 步的代数拆分同样常见：把“两个点之间的耦合项”（这里是距离 $j-i$）拆成只含单个下标的表达式， 是滑动窗口、单调栈、斜率优化这一族优化的共同起点。