审题可能会遇到的问题：认为所有人都必须参与拔河，但其实不用，只要符合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!=r1
for(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()操作稍微慢一些，因为它需要更多的模板解析和额外的参数推断。但通常情况下，这种差异不会非常显著，除非你在非常大的数据集上运行，并且对性能有极高的要求。