蓝桥杯每日真题 - 第7天

题目：（爬山）

题目描述（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 查找最接近的数值，从而找到两个不重叠子数组和之间的最小差值。