简答题 偏难
#21159

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

宝箱

时间限制: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的宝箱和一个价值为3的宝箱。

数据范围

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

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include&lt;bits/stdc++.h&gt; using namespace std; const int N = 1010; int a[N]; int n,k; int main(){ cin&gt;&gt;n&gt;&gt;k; for(int i=1;i&lt;=n;i++){ cin&gt;&gt;a[i]; } sort(a+1,a+n+1); int ans=0; for(int i=1;i&lt;=n;i++){ int sum=0; for(int j=i;j&gt;=1;j--){ if(a[i]-a[j]&lt;=k){ sum+=a[j]; }else break; } ans=max(ans,sum); } cout&lt;&lt;ans&lt;&lt;"\n"; }</pre>
解析

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