题目:(爬山)
题目描述(X届 C&C++ B组X题)
解题思路:
-
前缀和构造:为了高效地计算子数组的和,我们可以先构造前缀和数组
a
,其中a[i]
表示从第 1 个元素到第i
个元素的和。这样,对于任意区间[i, j]
的子数组和,可以通过a[j] - a[i-1]
快速得到。 -
枚举所有区间和:用双重循环枚举所有可能的区间
[i, j]
,将每个区间和存入multiset
s
中。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
表示元素数量。 -
使用
multiset
s
存储所有子数组的和,支持排序和快速查找。
-
-
辅助函数
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]
计算,并插入multiset
s
中。 -
使用
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
查找最接近的数值,从而找到两个不重叠子数组和之间的最小差值。