[GESP202406 四级] 宝箱
题目描述
小杨发现了 n n n 个宝箱,其中第 i i i 个宝箱的价值是 a i a_i ai。
小杨可以选择一些宝箱放入背包并带走,但是小杨的背包比较特殊,假设小杨选择的宝箱中最大价值为 x x x,最小价值为 y y y,小杨需要保证 x − y ≤ k x-y\leq k x−y≤k,否则小杨的背包会损坏。
小杨想知道背包不损坏的情况下,自己能够带走宝箱的总价值最大是多少。
输入格式
第一行包含两个正整数 n , k n,k n,k,含义如题面所示。
第二行包含 n n n 个正整数 a 1 , a 2 , … , a n a_1,a_2,\dots,a_n a1,a2,…,an,代表宝箱的价值。
输出格式
输出一个整数,代表带走宝箱的最大总价值。
样例 #1
样例输入 #1
5 1
1 2 3 1 2
样例输出 #1
7
提示
【样例解释】
在背包不损坏的情况下,小杨可以拿走两个价值为 2 2 2 的宝箱和一个价值为 3 3 3 的宝箱。
【数据范围】
对于全部数据,保证有 1 ≤ n ≤ 1000 1\leq n\leq 1000 1≤n≤1000, 0 ≤ k ≤ 1000 0\leq k\leq 1000 0≤k≤1000, 1 ≤ a i ≤ 1000 1\leq a_i\leq 1000 1≤ai≤1000。
#include <iostream>
#include <algorithm>
using namespace std;
int arr[2000];
int n,k,res=arr[0];
int main() {
cin>>n>>k;
for(int i=0; i<n; i++) {
cin>>arr[i];
}
sort(arr,arr+n);
for(int i=1; i<n; i++) {
int ind=0;
for(int j=0; j<=i; j++) {
if(arr[i]-arr[j]<=k) {
ind+=arr[j];
}
}
res=max(res,ind);
}
cout<<res;
return 0;
}
标签:arr,宝箱,int,GESP202406,样例,leq,四级,1000
From: https://blog.csdn.net/DXCcn/article/details/142286816