宝箱

题目描述

⼩杨发现了 个宝箱，其中第 个宝箱的价值是 。 ⼩杨可以选择⼀些宝箱放⼊背包并带⾛，但是⼩杨的背包⽐较特殊，假设⼩杨选择的宝箱中最⼤价值为 ，最⼩价值 为 ，⼩杨需要保证 ，否则⼩杨的背包会损坏。 ⼩杨想知道背包不损坏的情况下，⾃⼰能够带⾛宝箱的总价值最⼤是多少。

输入格式

第⼀⾏包含两个正整数 ，含义如题⾯所⽰。 第⼆⾏包含 个正整数 ，代表宝箱的价值。

输出格式

输出⼀个整数，代表带⾛宝箱的最⼤总价值。 3.2.4 样例1 1 5 1 2 1 2 3 1 2 1 7 3.2.5 样例解释 在背包不损坏的情况下，⼩杨可以拿⾛两个价值为 的宝箱和⼀个价值为 的宝箱。 3.2.6 数据范围 对于全部数据，保证有 。 3.2.7 参考程序 1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N = 1010; 4 int a[N]; 5 int n,k; 6 int main(){ 7 cin>>n>>k; 8 for(int i=1;i<=n;i++){ 9 cin>>a[i]; 10 } 11 sort(a+1,a+n+1); 12 int ans=0; 13 for(int i=1;i<=n;i++){ 14 int sum=0; 15 for(int j=i;j>=1;j--){ 16 if(a[i]-a[j]<=k){ 17 sum+=a[j]; 18 }else break; 19 } 20 ans=max(ans,sum); 21 } 22 cout<<ans<<"\n"; 23 }

样例输入 #1

1 5 1
2 1 2 3 1 2
1 7

样例输出 #1

样例解释 #1

在背包不损坏的情况下，⼩杨可以拿⾛两个价值为 的宝箱和⼀个价值为 的宝箱。

数据范围

对于全部数据，保证有 。

知识点与难度

本题涉及的知识点从属于 GESP 4级，难度等级：⭐⭐⭐ 。

测试点分布

生测试数据后，按实际 subtask 分组改写上表。