ZYF002 宝箱
大约 3 分钟
ZYF002 宝箱
【算法】 排序、双指针、前缀和
【C++】 sort、双指针、前缀和、long long
【难度】 普及-
一、题目简述
有 个宝箱,第 个宝箱的价值为 。你可以选择任意数量的宝箱,但要求所选宝箱中最大值与最小值的差不能超过 。求能达到的最大总价值。
数据范围:,,。
二、解题思路
分析
题目只限制所选宝箱的最大值和最小值之差 ≤ ,对中间的宝箱没有额外限制。也就是说,如果我们确定了所选宝箱的最小值为 ,那么所有价值在 范围内的宝箱都可以选。
直觉上,既然没有数量限制,我们应当把符合条件的宝箱全部选上,因为价值都是正数,选得越多总价值越大。
排序 + 滑动窗口
先对数组从小到大排序。排序后,问题转化为:
在排序后的数组中,找一段区间 ,使得 ,最大化区间内所有元素的和。
为什么一定是连续的一段?假设我们选了不连续的两个元素 和 (,差值 ≤ ),那么对于 和 之间的任意元素 ,一定有 ,所以 也满足差值条件。既然选了只会增加总价值,为什么不选呢?因此最优方案一定对应排序后的一段连续区间。
用滑动窗口维护这个区间:
- 右指针 逐渐扩展。
- 当 时,左指针 右移,直到差值 ≤ 。
- 窗口内元素的总和用前缀和快速计算:
pre[r] - pre[l-1]。 - 记录所有窗口中的最大总和。
手动模拟
以宝箱价值 [1, 2, 3, 1, 2], 为例。
首先排序:[1, 1, 2, 2, 3]
前缀和:pre = [0, 1, 2, 4, 6, 9]
| 步骤 | l | r | 窗口元素 | a[r]-a[l] | 操作 | 窗口和 | ans |
|---|---|---|---|---|---|---|---|
| 1 | 1 | 1 | [1] | 0 ≤ 1 | — | 1 | 1 |
| 2 | 1 | 2 | [1,1] | 0 ≤ 1 | — | 2 | 2 |
| 3 | 1 | 3 | [1,1,2] | 1 ≤ 1 | — | 4 | 4 |
| 4 | 1 | 4 | [1,1,2,2] | 1 ≤ 1 | — | 6 | 6 |
| 5 | 1 | 5 | [1,1,2,2,3] | 2 > 1 | l++ | — | — |
| 5 | 2 | 5 | [1,2,2,3] | 2 > 1 | l++ | — | — |
| 5 | 3 | 5 | [2,2,3] | 1 ≤ 1 | — | 7 | 7 |
| 5 | 3 | 5 | — | — | r 到头 | — | 7 |
最终答案为 7(选 [2, 2, 3],即第 3 到第 5 个宝箱)。
三、参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
long long a[N], pre[N]; // 注意数据可能很大,用 long long
int main() {
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + n + 1); // 从小到大排序
// 前缀和
for (int i = 1; i <= n; i++) {
pre[i] = pre[i - 1] + a[i];
}
int l = 1;
long long ans = 0;
for (int r = 1; r <= n; r++) {
// 缩左边界,直到差值满足条件
while (a[r] - a[l] > k) {
l++;
}
// 窗口内所有宝箱都可以选,总价值用前缀和求
ans = max(ans, pre[r] - pre[l - 1]);
}
cout << ans << endl;
return 0;
}四、复杂度分析
- 时间复杂度:。排序占主导,滑动窗口中每个元素进出各一次,为 。
- 空间复杂度:,用于存储数组和前缀和。
易错点
- 数据范围: 最大 , 个加起来可能超过
int范围(约 亿),必须用long long。 - 窗口维护:
while中 不断右移,每次 移动时 可能不动也可能移动多次,但总体每个元素最多移出一次。 - 的情况:当 时,要求所选宝箱价值完全相同(最大最小值差为 0),滑动窗口会自然处理(
a[r] - a[l] > 0时 右移直到 )。
