洛谷P2381题：双指针解决圆形奶牛间距的问题

一、问题分析

我们需要在环形排列的奶牛中找出两两之间的最大"最短距离"。这里的"最短距离"定义为顺时针和逆时针距离中的较小值。题目给出了相邻奶牛间的顺时针距离，所有奶牛形成一个闭合环。

二、算法思路

1. ‌环形问题处理‌：将圆形展开为两倍长度的线性数组

2. ‌前缀和数组‌：预处理计算累积距离

3. ‌双指针法‌：滑动窗口寻找满足条件的最大距离

4. ‌距离计算‌：对于任意两点，计算顺时针和逆时针距离取最小值

三、完整代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> distances(N);
    int total = 0;
    
    // 读取输入并计算总距离
    for(int i = 0; i < N; ++i) {
        cin >> distances[i];
        total += distances[i];
    }
    
    // 构建前缀和数组
    vector<int> prefix(2*N + 1, 0);
    for(int i = 1; i <= 2*N; ++i) {
        prefix[i] = prefix[i-1] + distances[(i-1)%N];
    }
    
    int max_min_dist = 0;
    int left = 0;
    
    // 双指针法寻找最大最小距离
    for(int right = 0; right < 2*N; ++right) {
        // 当前窗口距离
        int current_dist = prefix[right] - prefix[left];
        
        // 确保窗口距离不超过半圆
        while(current_dist > total/2) {
            left++;
            current_dist = prefix[right] - prefix[left];
        }
        
        // 更新最大最小距离
        max_min_dist = max(max_min_dist, current_dist);
    }
    
    cout << max_min_dist << endl;
    return 0;
}

四、算法详解

1. 输入处理

读取奶牛数量N和相邻奶牛间的顺时针距离，同时计算所有距离的总和。

2. 前缀和数组构造

构建长度为2N+1的前缀和数组，将环形问题转化为线性问题处理。

3. 双指针法核心逻辑

• 使用左右指针维护一个滑动窗口

• 确保窗口内距离不超过总距离的一半（即最短距离）

• 在滑动过程中记录最大的最短距离

4. 距离计算

对于任意两点，其最短距离是顺时针距离和逆时针距离中的较小值，而逆时针距离可以通过总距离减去顺时针距离得到。

五、总结

通过这个问题，我们学习了如何用双指针法高效解决环形距离问题。前缀和数组和滑动窗口技术的结合是解决这类问题的常见模式。掌握这种算法思想对处理环形数组、子数组和等问题都有很大帮助。