蓝桥杯拔河问题（前缀和与差分，multiset,区间冲突）

样例输入：
5
10 9 8 12 14
样例输出：
1

 

思路：

本题的题意是要找两个不重叠的区间对应的差值最小。多个区间和问题首先想到前缀和与差分，两个for循环遍历所有可能的区间，复杂度是o(n**2)。   接着就是要找两个差值最小，

引入stl关联容器multiset（它可以自动将插入的元素按从小到大的顺序排列，而且支持数值重复的元素，它的插入，删除和查找操作复杂度均为o(logn)),

s.lower_bound(a),用于查找在已排序号的集合s里的第一个大于等于值为a的元素，并返回它的迭代器，如果没找到则返回指向范围末尾的迭代器，upper_bound()是查找第一个>目标值的元素。

我们可以将每个区间值存入multiset,难点在于怎么找两个不重叠区间，首先第一个for循环删除以i为起点的区间，这样是为了避免[a,i][i,b]这种一个区间的终点是另一个区间的起点造成重叠的情况//至于查找以i 为终点的区间会不会与其他区间重叠呢，其实不会，因为在查到以i 为终点的区间时，前面的循环已经把所有起点<=i的都删除啦。最终复杂度时o(n**2*logn)不超时。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1005;
signed main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int n,a[N],s[N],ans=1e18;cin>>n;multiset <int> m;for(int i=1;i<=n;i++){cin>>a[i];//下标从 1 开始s[i]=s[i-1]+a[i];//下标从 1 开始(s[0]=0)，求前缀和}for(int i=1;i<n+1;i++){for(int j=i;j<n+1;j++){int t=s[j]-s[i-1];//表示i~j两闭区间m.insert(t);}}for(int i=1;i<n+1;i++){for(int j=i;j<n+1;j++){auto p=m.find(s[j]-s[i-1]);//这里注意要返回迭代器哈，如果直接删掉这个值的话，可能会把其他区间也删掉的 m.erase(p);}for(int j=i;j>=1;j--){int t=s[i]-s[j-1];auto p=m.lower_bound(t);if(p!=m.end()) ans=min(ans,abs(*p-t));//p是迭代器，相当于指针，*p则表示值 if(p!=m.begin()){p--;ans=min(ans,abs(*p-t));}}}cout<<ans<<endl;return 0;
}