选若干宝箱,要求所选价值最大值与最小值之差 ≤ k,求能带走的最大总价值。
有 n 个宝箱,第 i 个价值 aᵢ。小杨可以选一些带走,但背包要求:所选宝箱中最大价值 x 与最小价值 y 满足 x − y ≤ k,否则背包会损坏。
求背包不损坏的情况下,能带走宝箱的最大总价值。
排序连续区间枚举前缀和极差约束
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 n、k;第二行 n 个正整数 |
| 输出 | 最大总价值 |
| 数据范围 | 1 ≤ n ≤ 1000 |
| 数值范围 | 0 ≤ k ≤ 1000,1 ≤ aᵢ ≤ 1000 |
| 约束 | 所选集合的 max − min ≤ k |
先排序,再枚举所有跨度 ≤ 1 的区间。
| 步骤 | 内容 |
|---|---|
| 原数组 | 1, 2, 3, 1, 2 |
| 排序后 | 1, 1, 2, 2, 3 |
| 下标 | 0, 1, 2, 3, 4 |
| 区间 | 元素 | 跨度 | 是否 ≤ 1 | 区间和 |
|---|---|---|---|---|
| [0,0] | 1 | 0 | ✅ | 1 |
| [0,1] | 1, 1 | 0 | ✅ | 2 |
| [0,2] | 1, 1, 2 | 2 − 1 = 1 | ✅ | 4 |
| [0,3] | 1, 1, 2, 2 | 2 − 1 = 1 | ✅ | 6 |
| [0,4] | 1, 1, 2, 2, 3 | 3 − 1 = 2 | ❌ | — |
| [1,2] | 1, 2 | 1 | ✅ | 3 |
| [1,3] | 1, 2, 2 | 1 | ✅ | 5 |
| [2,3] | 2, 2 | 0 | ✅ | 4 |
| [2,4] | 2, 2, 3 | 3 − 2 = 1 | ✅ | 7 |
| [3,4] | 2, 3 | 1 | ✅ | 5 |
| [4,4] | 3 | 0 | ✅ | 3 |
区间 [2,4] = {2, 2, 3},跨度 3 − 2 = 1 ≤ 1
总和 = 2 + 2 + 3 = 7
另一个候选 [0,3] = {1, 1, 2, 2} 总和 6,更小
✅ 答案 7
题面说"拿走两个价值为 2 的宝箱和一个价值为 3 的宝箱"
正是 {2, 2, 3},总和 7 ✓
注意 aᵢ = 1 的两个宝箱没被选中——因为一旦选它们,跨度就变成 3 − 1 = 2 > k
✅ 完全吻合
| 情形 | 数据 | 分析 | 答案 |
|---|---|---|---|
| k = 0 | a = [5, 5, 3] | 跨度必须为 0 → 只能选全部相同的值 | 10(两个 5) |
| 只有一个宝箱 | a = [7] | 必选 | 7 |
| 全部相同 | a = [4, 4, 4] | 跨度 0,全选 | 12 |
| k 足够大 | a = [1, 100], k = 99 | 跨度 99 ≤ 99,可以全选 | 101 |
排序后双层循环枚举左右端点,用前缀和求和
a[r] - a[l] > k 就停止(再往右只会更大)。随着 l 右移,r 也单调右移,用滑动窗口维护区间和
a[l] 变大,窗口右端 r 的最远位置只会更远或不变,所以 r 可以继承上一轮的位置不回头,整体是 O(n)。| 方案 | 本题运算量 | n = 10⁵ 时 |
|---|---|---|
| 排序 + 枚举 | 约 5 × 10⁵ | 约 5 × 10⁹(超时) |
| 双指针 | 约 10³ | 约 1.7 × 10⁶(可行) |
第一行输入价值和 k(用 | 分隔),程序会排序并枚举所有跨度 ≤ k 的区间。
点按钮开始 →
#include <bits/stdc++.h> using namespace std; int a[1005]; long long pre[1005]; int main() { int n, k; scanf("%d %d", &n, &k); for (int i = 0; i < n; i++) scanf("%d", &a[i]); sort(a, a + n); // 排序后,最优解对应一段连续区间 // 前缀和:pre[i] = a[0] + ... + a[i-1] pre[0] = 0; for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + a[i]; long long ans = 0; for (int l = 0; l < n; l++) { for (int r = l; r < n; r++) { if (a[r] - a[l] > k) break; // 跨度超标,再往右只会更大 long long sum = pre[r + 1] - pre[l]; // 区间 [l, r] 的和 if (sum > ans) ans = sum; } } printf("%lld\n", ans); return 0; }
break?因为数组已经升序,随着 r 增大 a[r] 只增不减,所以 a[r] - a[l] 也会单调增大。一旦超标,后面全部超标,直接 break 就能省掉大量无用检查。| 代码 | 作用 | 为什么这样写 |
|---|---|---|
sort(a, a + n) | 排序 | 让"跨度"对应连续区间的端点差 |
pre[i+1] = pre[i] + a[i] | 前缀和 | 使区间和查询变成一次减法 |
if (a[r] - a[l] > k) break; | 跨度检查 | 超标就停,因为后面更大 |
pre[r+1] - pre[l] | 区间和 | 注意上界是 r+1 而不是 r |
< k(题目是 ≤ k);③ 前缀和下标写错:区间 [l, r] 的和是 pre[r+1] - pre[l]。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
5 1 | 7 | 题面样例 |
1 0 | 7 | 单个宝箱,必选 |
3 0 | 10 | k = 0 只能选相同的值,两个 5 得 10 |
3 100 | 6 | k 很大,全部可以选 |
4 2 | 40 | 相邻两数相差 10 > k = 2,任何两个都不能同选,最大为 40 |
3 5 | 11 | 6 − 1 = 5 ≤ 5,三个都选得 11 |
max − min ≤ k,包含等于的情况。pre[r+1] − pre[l]。需要存数组与前缀和数组。
✅ 约 50 万次操作,瞬间完成。如果 n 达到 10⁵,就要改用双指针滑动窗口。
// 核心结论:排序后,满足"极差 ≤ k"的最优子集一定对应一段连续区间 // 证明直觉:若最优集合的最小值在位置 l、最大值在位置 r, // 则把 [l, r] 中所有元素都选上,极差不变(仍是 a[r]-a[l]), // 但总和变大 -> 所以连续区间必然不劣于原集合。 // 前缀和求区间和 long long rangeSum(int l, int r) { return pre[r+1] - pre[l]; } // 双指针 O(n) 版本(n 很大时用) long long best = 0, cur = 0; int r = 0; for (int l = 0; l < n; l++) { while (r < n && a[r] - a[l] <= k) { cur += a[r]; r++; } best = max(best, cur); cur -= a[l]; // 左端点右移,去掉 a[l] } // 类似的"极差约束"题目都可以用这个套路
把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。
| 能力点 | 本题怎么用 | 还能迁移到 |
|---|---|---|
| 排序 + 连续区间 | 极差约束 → 排序后枚举区间 | 选数最大化、预算分配、区间最值 |
| 前缀和求区间和 | O(1) 查询 | 所有需要反复求区间和的题 |
| 单调性 break | 差值单调 → 可提前终止 | 优化枚举的常用技巧 |