拔河

问题描述

小明是学校里的一名老师，他带的班级共有 $n$ 名同学，第 $i$ 名同学力量值为 $a_i$。在闲暇之余，小明决定在班级里组织一场拔河比赛。
为了保证比赛双方实力尽可能相近，需要在这 $n$ 名同学中挑选出两个队伍，队伍内的同学编号连续：${a_{l_1}, a_{l_1+1}, \dots, a_{r_1}}$ 和 ${a_{l_2}, a_{l_2+1}, \dots, a_{r_2}}$，其中 $l_1 \le r_1 < l_2 \le r_2$。
两个队伍的人数不必相同，但是需要让队伍内的同学们的力量值之和尽可能相近。请计算出力量值之和差距最小的挑选队伍的方式。

输入格式

输入共两行。
第一行为一个正整数 $n$。
第二行为 $n$ 个正整数 $a_i$。

输出格式

输出共一行，一个非负整数，表示两个队伍力量值之和的最小差距。

样例输入

5
10 9 8 12 14

样例输出

1

样例说明

其中一种最优选择方式：
队伍 1：${a_1, a_2, a_3}$，队伍 2：${a_4, a_5}$，力量值和分别为 $10+9+8=27$，$12+14=26$，差距为 $|27-26|=1$。

#include <iostream>
#include<vector>
#include<set>
using namespace std;
int main()
{
    int n,ans=9999999;
    cin>>n;
    vector<int>arr(n+1,0);
    set<int> s;
    for(int i=1;i<=n;i++)
    cin>>arr[i];
    for(int i=1;i<=n;i++)
    arr[i]+=arr[i-1];
    for(int r1=n-1;r1>=1;r1--)
    {
        for(int i=r1+1;i<=n;i++)
        s.insert(arr[i]-arr[r1]);
        for(int l1=1;l1<=r1;l1++)
        {
            int left_sum=arr[r1]-arr[l1-1];
            // 3. 在 Set 里找最接近 left_sum 的值
            // lower_bound 找到第一个 >= left_sum 的位置
            auto it = s.lower_bound(left_sum);

            // 情况 A: 找到了 >= left_sum 的值，算一下差值
            if (it != s.end()) {
                ans = min(ans, abs(*it - left_sum));
            }

            // 情况 B: 它前面的那个值（即 < left_sum 的最大值），也要算一下
            // 因为最接近的值可能是比它大的，也可能是比它小的
            if (it != s.begin()) {
                auto prev_it = prev(it); // 获取迭代器的前一个位置
                ans = min(ans, abs(*prev_it - left_sum));
        }
    }
    }
cout<<ans;
}