2024年6月C++编程等级认证四级编程题真题:宝箱

CCF-GESP四级

这是一道非常经典的双指针 + 前缀和的题目，叫做‘宝箱问题’。题目大意是：我们有 n 个宝箱，每个有价值 ai，我们要选一些宝箱，使得它们的最大值和最小值的差不超过 k，同时让总价值最大。”

• “首先，我们来想一个关键点：如果把数组排序，那么任何一个连续的子数组 [left, right] 的最大值就是 a[right]，最小值就是 a[left]。这样，条件 max - min ≤ k 就简化成 a[right] - a[left] ≤ k。”

• “所以，我们第一步肯定是排序，这是解题的基础。”

• “原代码的思路是对的，它排序后，对每个 i 向前找所有满足 a[i] - a[j] ≤ k 的 j，然后累加求和。”

• “但这样做时间复杂度是 O(n²)，因为每个 i 都要往前遍历一遍。当 n=1000 时，1000²=1e6 次运算，虽然能过，但我们可以优化到 O(n)。”

• 排序：“先排序数组，让问题变得可解。”

• 前缀和：“我们预处理一个前缀和数组 pre_sum，这样任意区间 [left, i] 的和就可以用 pre_sum[i] - pre_sum[left-1] 快速得到，时间复杂度 O (1)。”

• 双指针滑动窗口：“我们用 i 作为右指针，left 作为左指针。

• 对于每个 i，我们移动 left 直到 a[i] - a[left] ≤ k。

• 因为数组是排序好的，所以一旦 a[i] - a[left] > k，left 只能向右移动，不会回退，这样整个过程是 O(n) 的。”

“我们用样例输入来走一遍：输入：5 1，数组 [1,2,3,1,2]排序后：[1,1,2,2,3]前缀和：[0,1,2,4,6,9]

• 当 i=5（a [i]=3），我们检查 a[i]-a[left]：

• left=1 时，3-1=2>1 → left++

• left=2 时，3-1=2>1 → left++

• left=3 时，3-2=1≤1 → 停止

• 区间 [3,5] 的和是 pre_sum[5] - pre_sum[2] = 9-2=7 → 这就是答案。”

“接下来，我们看优化后的代码：

• 头文件和变量定义：long long pre_sum 是为了防止溢出。

• 排序：sort(a+1, a+n+1) 让数组有序。

• 前缀和计算：pre_sum[i] = pre_sum[i-1] + a[i]。

• 双指针遍历：for (int i=1; i<=n; i++) 枚举右指针，while (a[i]-a[left]>k) left++ 移动左指针，然后计算区间和更新答案。”

• “时间复杂度：排序是 O(n log n)，双指针遍历是 O(n)，整体是 O(n log n)。”

• “空间复杂度：O(n) 用于存储前缀和数组。”