洛谷P2381题：前缀和+双指针算法解决圆圆舞蹈

一、题目解读

洛谷P2381题要求在一个环形轨道上，给定每个位置的距离，寻找最长的连续路径（不超过半圆周长），并计算该路径的最小距离。题目关键在于处理环形结构，并高效计算子路径距离，属于算法设计与数据结构结合的经典问题。

二、解题思路

采用“前缀和+双指针”策略：

1. 前缀和预处理：构建2N长度的数组，存储环形轨道的循环前缀和，避免环形边界判断；

2. 滑动窗口优化：双指针left/right移动，维护窗口距离不超过总距离一半，动态更新最大最小距离；

3. 边界处理：利用取模运算实现环形索引，简化代码逻辑。

三、解题步骤

1. 输入与初始化：读入N个点距离，计算总距离total；

2. 构建前缀和数组：扩展至2N长度，允许指针滑动跨越起点；

3. 双指针扫描：right递增，left动态调整（若窗口距离超限则左移），实时计算当前窗口距离；

4. 更新结果：记录所有合法窗口中的最大距离（即最小可行路径长度）；

5. 输出答案：最终max_min_dist为所求结果。

四、代码与注释

#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];
    }
    
    // 构建前缀和数组（扩展2N倍）
    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;
}

五、总结

该解法巧妙利用前缀和解决环形路径求和问题，双指针滑动窗口降低时间复杂度至O(N)，避免暴力枚举。代码简洁且高效，适用于大规模数据场景。进一步优化方向可考虑二分查找优化窗口收缩，但当前方案已满足题目需求。