【蓝桥杯省赛B组】（洛谷P10429）拔河题目解题思路与代码解析（C++实现）

一、题目解读

2024年蓝桥杯省赛B组“拔河”题目（对应洛谷P10429）要求处理一个数列，通过划分区间使两队实力差最小。题目核心是将数列分段，计算各区间和的差值，并找出全局最小差。此问题需转化为区间求和与差值优化问题，考验选手对前缀和与双指针算法的灵活运用。

二、解题思路

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

1. 前缀和预处理：计算数组前缀和，将区间和转换为 prefix[r] - prefix[l-1]，降低单次求和复杂度。

2. 生成所有区间和：遍历所有可能区间，记录其和及边界（右端点r,左端点l）。

3. 排序与双指针优化：按区间和升序排序，通过双指针滑动，确保不重叠（sums[i-1].right < sums[i].left），动态更新最小差值。

此思路将暴力O(n^2)优化至O(nlogn)，突破时间限制。

三、解题步骤详解

1. 输入与初始化：读取n及数组a，创建n+1长度的前缀和数组prefix（含初始0元素）。

2. 计算前缀和：通过循环累积前缀和，便于后续O(1)获取区间和。

3. 生成区间和列表：双层循环遍历所有区间，存入sums向量（按和、右端点、左端点配对）。

4. 排序区间：利用sort函数按和升序排列，为双指针创造条件。

5. 双指针查找：从相邻区间对中，筛选不重叠且差值最小的组合，更新min_diff。

6. 输出结果：最终输出min_diff。

四、代码与注释

int main() {  
    ios::sync_with_stdio(false);  
    cin.tie(nullptr);      // 加快输入输出速度  

    int n;  
    cin >> n;  
    vector<int> a(n);  
    for (int i = 0; i < n; ++i) cin >> a[i];      // 读入原始数组  

    vector<int> prefix(n + 1, 0);  
    for (int i = 1; i <= n; ++i)  
        prefix[i] = prefix[i - 1] + a[i - 1];      // 计算前缀和  

    int min_diff = INT_MAX;  

    // 预处理所有可能的区间和及其边界  
    vector<pair<int, pair<int, int>>> sums;  
    for (int l = 1; l <= n; ++l) {  
        for (int r = l; r <= n; ++r) {  
            sums.emplace_back(prefix[r] - prefix[l-1], make_pair(r, l));  
        }  
    }  

    // 按区间和升序排序  
    sort(sums.begin(), sums.end());  

    // 双指针寻找最小差值  
    for (int i = 1; i < sums.size(); ++i) {  
        // 确保区间不相交：前区间的右边界 < 后区间的左边界  
        if (sums[i-1].second.first < sums[i].second.second) {  
            min_diff = min(min_diff, sums[i].first - sums[i-1].first);  
        }  
    }  

    cout << min_diff << endl;  
    return 0;  
}

五、总结

本题关键在于将区间差值问题转化为有序序列的双指针查找。通过前缀和减少重复计算，排序后利用区间不重叠特性，高效锁定最优解。此解法兼具时间效率与逻辑清晰度，是处理区间优化问题的典型范例。掌握此类技巧可显著提升竞赛中复杂问题的解决能力。

参考：2024年蓝桥杯省赛B组拔河题解