题目链接

丢手绢 - 牛客网

题目大意

牛客幼儿园的小朋友们围成一个圆圈玩丢手绢。已知相邻两个小朋友之间的顺时针距离，求离得最远的两个小朋友的距离（距离定义为沿圆圈顺时针或逆时针走的最近距离）。

换句话说：给定一个环，每条边的长度已知，求环上两点之间的最短路径的最大值（即环的直径）。

输入输出

输入：

• 第一行一个整数 N，表示小朋友的数量。
• 接下来 N 行，每行一个整数，表示相邻两个小朋友之间的顺时针距离。最后一行是第 N 个小朋友顺时针到第 1 个小朋友的距离。

输出：

• 一个整数，表示离得最远的两个小朋友的距离。

样例：

→3
→1
→2
→3
3

三个小朋友围成的圆周长 = 1 + 2 + 3 = 6。两点之间的最短距离分别为：1、2、3。最大值为 3。

思路分析

1. 破环为链

对于环形问题，最常用的技巧是破环为链：把数组复制一遍拼接在末尾，这样原本的「绕回起点」就变成了直链上的连续区间。

设原数组为 a[1..N]，复制后 a[N+1..2N] = a[1..N]。

总周长记为 sum。从某点出发，沿顺时针走的距离一旦超过 sum/2，那逆时针方向就更短了——所以我们只关心顺时针距离 ≤ sum/2 的区间。

2. 核心结论

在环上，任意两点之间的最短距离不可能超过 sum/2。

证明很直观：如果顺时针距离 > sum/2，那么逆时针距离 = sum - 顺时针距离 < sum/2，最短距离取小的那个，所以始终 ≤ sum/2。

因此，答案就是所有 ≤ sum/2 的区间和 中的最大值。

3. 滑动窗口（双指针）

问题转化为：在长度为 2N 的数组上，找到一个和不超过 sum/2 的连续子数组，使得和尽可能大——但子数组的起点只能在 [1, N] 范围内（因为环上只有 N 个不同的起点）。

我们维护两个指针：

• i：窗口左端点（枚举的起点）
• j：窗口右端点（不断向右扩展）
• cnt：当前窗口 [i, j) 的区间和

对于每个 i：

1. 不断将 j 右移，将 a[j] 加入 cnt，直到再加入下一个数就会超过 sum/2。
2. 此时 cnt 就是起点 i 对应的最大可行区间和，更新答案。
3. 左端点 i 移出窗口，cnt -= a[i]。

关键细节：j 不需要回退！因为 i 右移后区间和只会变小，j 可以继续向右——这就是滑动窗口 O(N) 的保证。

代码实现

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200009;
int a[MAXN];        // 破环为链后的数组，长度 2N

int main() {
    int N;
    long long sum = 0;
    cin >> N;
    
    for (int i = 1; i <= N; i++) {
        cin >> a[i];
        a[i + N] = a[i];   // 破环为链
        sum += a[i];
    }
    
    long long cnt = 0;     // 当前窗口区间和
    long long ans = 0;     // 最终答案
    int j = 1;             // 右指针
    
    for (int i = 1; i <= N; i++) {
        // 扩展右端点直到不能再加
        while (j <= 2 * N) {
            if (cnt + a[j] <= sum / 2)
                cnt += a[j];
            else
                break;
            j++;
        }
        
        // cnt 就是起点为 i 时 ≤ sum/2 的最大区间和
        ans = max(ans, cnt);
        
        // 左端点移出窗口
        cnt -= a[i];
    }
    
    cout << ans << endl;
    return 0;
}

复杂度分析

图解

假设样例 N=3, a=[1, 2, 3]，sum=6，sum/2=3：

破环为链后：[1, 2, 3, 1, 2, 3]

i=1: j 扫过 [1,2,3], cnt=1+2=3     → ans=3, 移出 a[1]=1
i=2: j 继续扫 [1,2,3], cnt=2+1=3   → ans=3, 移出 a[2]=2
i=3: cnt=3 仍 ≤3                   → ans=3, 移出 a[3]=3
最终 ans = 3 ✓

总结

这道题的核心考点是：

1. 破环为链 — 处理环形问题的经典技巧
2. 滑动窗口（双指针） — 维护单调性，做到 O(N) 时间复杂度
3. 数学洞察 — 圆上最短距离不可能超过半周长

类似题目：环形最大子数组和、石油管道问题等，都是这个套路。