免费h5响应式网站搭建,上海公司招聘,开发电子商务系统的五个步骤,公众号软文怎么写题目#xff1a;#xff08;爬山#xff09;
题目描述#xff08;X届 CC B组X题#xff09; 解题思路#xff1a; 前缀和构造#xff1a;为了高效地计算子数组的和#xff0c;我们可以先构造前缀和数组 a#xff0c;其中 a[i] 表示从第 1 个元素到第 i 个元素的…题目爬山
题目描述X届 CC 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
#includebits/stdc.h
using namespace std;
const int N 1e310;
long long a[N];
int n;
multisetlong longs;
long long minn(long long a,long long b){if(ab) return a;else return b;
}
int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);//取消同步流cinn;for(int i 1;in;i) {cina[i];a[i]a[i-1];//构造前缀和}for(int i 1;in;i){for(int j i;jn;j){s.insert(a[j]-a[i-1]);//枚举右区间所有情况先加入set中}}long long res 1e9;//这里的i是第一个区间的右端点for(int i 1;in;i){//删除掉以i作为右区间第一个数字的情况for(int j i;jn;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;ji;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前面一点}}}coutresendl;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 查找最接近的数值从而找到两个不重叠子数组和之间的最小差值。
