简答题 偏难
#18349

宝箱 时间限制:1.0 s 内存限制:512.0 MB 题面描述 小杨发现了n个宝箱,其中第i个宝箱的价值是ai。 小杨可以选择一些宝箱放入背包并带走,但是小杨…

宝箱

时间限制:1.0 s

内存限制:512.0 MB

题面描述

小杨发现了n个宝箱,其中第i个宝箱的价值是ai。

小杨可以选择一些宝箱放入背包并带走,但是小杨的背包比较特殊,假设小杨选择的宝箱中最大价值为x,最小价值为y,小杨需要保证x−y≤k,否则小杨的背包会损坏。

小杨想知道背包不损坏的情况下,自己能够带走宝箱的总价值最大是多少。

输入格式

第一行包含两个正整数n,k,含义如题面所示。

第二行包含n个正整数a1,a2 , . . . , an,代表宝箱的价值。

输出格式

输出一个整数,代表带走宝箱的最大总价值。


输入样例

5 1
1 2 3 1 2

输出样例

7


样例解释

在背包不损坏的情况下,小杨可以拿走两个价值为 2 22 的宝箱和一个价值为 3 33 的宝箱。

数据范围

对于全部数据,保证有 1 ≤ n ≤ 1000 , 0 ≤ k ≤ 1000 , 1 ≤ ai ≤ 1000

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:python;toolbar:false">N = 1010 a = [0] * N def main(): n, k = map(int, input().split()) aa = input().split() for i in range(1, n + 1): a[i] = int(aa[i-1]) a[1:n + 1] = sorted(a[1:n + 1]) ans = 0 for i in range(1, n + 1): sum = 0 for j in range(i, 0, -1): if a[i] - a[j] &lt;= k: sum += a[j] else: break ans = max(ans, sum) print(ans) if __name__ == "__main__": main()</pre><p><br/></p>
解析

比较容易想到的做法是用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)。