题目：（爬山）
题目描述（X届 C&C++ B组X题）
解题思路：
-
前缀和构造：为了高效地计算子数组的和，我们可以先构造前缀和数组
a，其中a[i]表示从第 1 个元素到第i个元素的和。这样，对于任意区间[i, j]的子数组和，可以通过a[j] - a[i-1]快速得到。 -
枚举所有区间和：用双重循环枚举所有可能的区间
[i, j]，将每个区间和存入multisets中。multiset支持快速查找、插入和删除，且自动排序，是处理该问题的合适选择。 -
最小差值的计算：
-
遍历每一个位置
i，将该位置作为第一个区间的右端点。 -
在
multiset中删除以i作为右端点的所有区间和，以避免区间重叠。 -
然后遍历每一个可能的左端点
j，计算第一个区间[j, i]的和k = a[i] - a[j-1]。 -
使用
lower_bound查找s中最接近k的区间和，计算绝对差值，并更新最小差值res。 -
在
lower_bound查找时，考虑s中前后两个元素，以确保找到最接近k的数值。
-
-
输出结果：最终输出最小的差值
res。
代码实现（C++）：
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3+10;
long long a[N];
int n;
multiset<long long>s;
long long minn(long long a,long long b){
if(a<b) return a;
else return b;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);//取消同步流
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++){
s.insert(a[j]-a[i-1]);//枚举右区间所有情况先加入set中
}
}
long long res = 1e9;
//这里的i是第一个区间的右端点
for(int i = 1;i<n;i++){
//删除掉以i作为右区间第一个数字的情况
for(int j = i;j<=n;j++){
// auto p = s.find(a[j]-a[i-1]);
// s.erase(p);
auto k = a[j] - a[i-1];
s.erase(s.find(k));
}
//这里的j是第一个区间的左端点
for(int j = 1;j<=i;j++){
auto k = a[i] - a[j-1];
//找到又区间中最接近k的位置，用lower_bound(s.begin(),s.end(),k)
//会慢很多，不建议
auto p = s.lower_bound(k);
if(p!=s.end()){
res = minn(res,abs(*p-k));
}
if(p!=s.begin()){
p--;
res = minn(res,abs(*p-k));
//lower_bound返回的是第一个>=k的数字，因此绝对值最小的情况也可能在p前面一点
}
}
}
cout<<res<<endl;
return 0;
}代码分析：
-
头文件和常量定义
-
引入头文件
#include <bits/stdc++.h>，方便使用标准库的各种数据结构和算法。 -
定义常量
N为数组的最大长度（设置为 1000）。 -
定义数组
a[N]用于存储前缀和，n表示元素数量。 -
使用
multisets存储所有子数组的和，支持排序和快速查找。
-
-
辅助函数
minn-
minn函数用于返回两个数中的较小值，这个函数会在更新最小差值时使用。 -
使用辅助函数代替
std::min可以提高代码可读性。
-
-
初始化和输入
-
ios::sync_with_stdio(0);、cin.tie(0);和cout.tie(0);是用于加快 I/O 操作的优化。 -
读取输入
n和数组元素，构造前缀和a[i] += a[i - 1];，a[i]表示从第一个元素到第i个元素的和。 -
构造前缀和后，可以通过
a[j] - a[i - 1]快速获得区间[i, j]的和。
-
-
枚举所有区间和并加入
multiset-
双重循环枚举所有可能的区间
[i, j]。 -
每个区间和通过
a[j] - a[i - 1]计算，并插入multisets中。 -
使用
multiset是因为它支持自动排序和快速查找最接近的值。
-
-
枚举区间、删除重叠区间和查找最小差值
-
外层循环的
i表示第一个区间的右端点。 -
内部循环先删除以
i为右端点的所有区间和，避免第一个区间和第二个区间重叠。 -
对于当前右端点
i，再枚举每个可能的左端点j，计算第一个区间[j, i]的和k = a[i] - a[j-1]。 -
使用
lower_bound查找s中最接近k的值。由于lower_bound返回的是第一个大于等于k的迭代器p，所以还需要检查p的前一个元素，以找到绝对差值最小的情况。 -
最小差值存储在
res中。
-
难度分析
⭐️⭐️⭐️⭐️
总结
-
使用前缀和快速计算子数组和。
-
使用
multiset存储所有子数组和，以支持有序查找和删除操作。 -
通过双重循环枚举区间和，并使用
lower_bound查找最接近的数值，从而找到两个不重叠子数组和之间的最小差值。