蓝桥杯2024省赛B组拔河问题：前缀和与双指针解法详解

6天前比赛题解67

一、问题背景

题目要求将n个人分成两组进行拔河比赛，每组必须连续排在一起，目标是让两组的总力量差值最小。这是典型的区间分割问题，需要高效计算所有可能的连续区间和。

二、核心算法思路

前缀和预处理：快速计算任意区间的和
枚举所有区间：记录每个区间的和及其边界位置
排序优化：将区间和按大小排序
双指针扫描：寻找不相交区间的最小差值

三、完整代码解析（带注释）

int main() {
    ios::sync_with_stdio(false);  // 关闭同步提升IO速度
    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;
}