简答题
偏难
#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,代表宝箱的价值。
输出格式
输出一个整数,代表带走宝箱的最大总价值。
输入样例
输出样例
样例解释
在背包不损坏的情况下,小杨可以拿走两个价值为2的宝箱和一个价值为3的宝箱。
数据范围
对于全部数据,保证有1≤n≤1000,0≤k≤1000,1≤ai≤1000。
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int a[N];
int n,k;
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
}
sort(a+1,a+n+1);
int ans=0;
for(int i=1;i<=n;i++){
int sum=0;
for(int j=i;j>=1;j--){
if(a[i]-a[j]<=k){
sum+=a[j];
}else break;
}
ans=max(ans,sum);
}
cout<<ans<<"\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)。