[GESP202406 四级] 宝箱
GESP编程共123题，本题是整站第1417题，已经有人完成了本题，加油！
题目描述
小杨发现了 n 个宝箱，其中第 i 个宝箱的价值是 ai。
小杨可以选择一些宝箱放入背包并带走，但是小杨的背包比较特殊，假设小杨选择的宝箱中最大价值为 x，最小价值为 y，小杨需要保证 x−y≤k，否则小杨的背包会损坏。
小杨想知道背包不损坏的情况下，自己能够带走宝箱的总价值最大是多少。
输入格式
第一行包含两个正整数 n,k，含义如题面所示。
第二行包含 n 个正整数 a1,a2,…,an，代表宝箱的价值。
输出格式
输出一个整数，代表带走宝箱的最大总价值。
输入输出样例
输入 #1
5 1 1 2 3 1 2
输出 #1
7
说明/提示
【样例解释】
在背包不损坏的情况下，小杨可以拿走两个价值为 2 的宝箱和一个价值为 3 的宝箱。
【数据范围】
对于全部数据，保证有 1≤n≤1000，0≤k≤1000，1≤ai≤1000。
别灰心，再试一次！
真题解析
【考纲知识点】
排序算法
【解题思路】
比较容易想到的做法是用O(n)的复杂度枚举一个a[i]作为最大值x，然后用O(n)的复杂度枚举另一个值a[j]作为最小值y，最后用O(n)的复杂度枚举数组，计算一下值处于[x,y]的元素总和sum，算出来的总和与ans取最大值即可，但是这样的做法是O(n^3)的，没有办法拿到满分；
我们发现，之所以我们最后需要O(n)的复杂度枚举数组的元素计算总和，是因为我们不知道数值处在[x,y]范围内的元素总和是多少，所以需要枚举计算。
为了解决这个问题，我们可以先将数组从小到大排序，这样一来，数组中的每个子区间[j,i]的左右端点的值a[j]、a[i]分别就对应了我们枚举的最小值x，和最大值y，又因为数组是有序的，因此，数值处于[x,y]范围内的元素正好就是区间[j,i]内的所有元素，这样一来，我们就可以在向前枚举a[j]（也就是最小值y）的同时，顺便计算区间[j,i]内的元素总和sum，时间复杂度降为了O(n^2)。
参考程序
本站题目仅供学习，GESP版权归CCF所有，如有侵权请联系删除。站长陈老师QQ及微信:208234。