审题可能会遇到的问题：认为所有人都必须参与拔河，但其实不用，只要符合l1<=r1<l2<=r2就行，不一定要全部人上场，比如只上场a1和a2他们的力量差是1其实也可以。
正解思路：前缀和+枚举+二分。枚举左区间，利用二分来选择右区间。时间复杂度O(N^2*logn)能满足题目要求。先利用前缀和求出任意两点间的区间和，然后存入multiset中。然后枚举左区间的右端点，期间先删除以这个右端点为左端点的右区间，然后再枚举左区间，在所有右区间中，找到和左区间值最近的右区间（一个大于它一个小于它），然后计算差值，记录答案。
- 使用前缀和能化简求任意区间和的过程，不用前缀和复杂度为O(n^3)超时。
- 用lower_bound(s.begin(),s.end(),k)速度会比s.lower_bound(k) 慢非常多，使用会超时，原因见文末。
- 这道题输入较多，需要取消输入输出同步流，否则会超时
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define pp ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
const int N = 1e3+10;//不去重的排序集合
multiset<int>s;int a[N];void solve(){//这道题数据量比较多，如果不取消同步流会超时pp;int n;cin>>n;//计算前缀和，方便计算任意区间之和for(int i=1;i<=n;i++)cin>>a[i],a[i]+=a[i-1];//计算区间之和for(int i=1;i<=n;i++)for(int j=i;j<=n;j++)//j==i时，前缀和的差分是原数列//j!=i时，是[i,j]之间的区间和s.insert(a[j]-a[i-1]);int res = INT_MAX;//i是左区间的右端点,注：左区间的右端点不能等于n，因为l2!=r1for(int i=1;i<n;i++){/*删除以i为左端点的所有区间，因为接下来选择右区间用不到，右区间是从i+1开始选择并且在i往后拓展时，如果保留之前的以i为左端点的右区间之和，会干扰正确答案剩下的s就是所有满足以i为左区间右端点的右区间。*/for(int j=i;j<=n;j++){auto add = a[j]-a[i-1];s.erase(s.find(add));}//枚举左区间，选择正确的右区间，计算力量值之和差距最小for(int j=1;j<=i;j++){//左区间之和auto k = a[i]-a[j-1];//寻找与左区间值最近的右区间/**lower_bound(s.begin(), s.end(), k)比s.lower_bound(k)慢很多*/auto p = s.lower_bound(k);//大于等于k最近的右区间if(p!=s.end())res = min(res,abs(*p-k));//小于k最近的右区间if(p!=s.begin()){p--;res = min(res,abs(*p-k));}}}cout<<res<<endl;
}signed main(){int T=1;while(T--)solve();return 0;
}用lower_bound(s.begin(),s.end(),k)速度会比s.lower_bound(k) 慢非常多的原因：
这是因为 lower_bound() 函数是通用的，适用于各种容器类型，而 s.lower_bound(k) 是特定于某个具体容器类型（比如set 或 map）的成员函数。在调用 lower_bound() 时，编译器必须解析和调用一个通用的函数模板，而s.lower_bound(k) 可以直接在编译时确定具体容器类型，并且可以根据该类型进行一些优化。这种差异可能会导致通用的 lower_bound()操作稍微慢一些，因为它需要更多的模板解析和额外的参数推断。但通常情况下，这种差异不会非常显著，除非你在非常大的数据集上运行，并且对性能有极高的要求。
