题目描述
小杨发现了 𝑛 个宝箱,其中第 𝑖 个宝箱的价值是 𝑎𝑖。
小杨可以选择一些宝箱放入背包并带走,但是小杨的背包比较特殊,假设小杨选择的宝箱中最大价值为 𝑥,最小价值为 𝑦,小杨需要保证 𝑥−𝑦≤𝑘,否则小杨的背包会损坏。
小杨想知道背包不损坏的情况下,自己能够带走宝箱的总价值最大是多少。
输入格式
第一行包含两个正整数 𝑛,𝑘,含义如题面所示。
第二行包含 𝑛n 个正整数 𝑎1,𝑎2,…,𝑎𝑛,代表宝箱的价值。
输出格式
输出一个整数,代表带走宝箱的最大总价值。
输入输出样例
输入 #1
5 1 1 2 3 1 2
输出 #1
7
说明/提示
【样例解释】
在背包不损坏的情况下,小杨可以拿走两个价值为 2 的宝箱和一个价值为 3 的宝箱。
【数据范围】
对于全部数据,保证有 1≤𝑛≤1000,0≤𝑘≤1000,1≤𝑎𝑖≤1000。
对数组进行排序,然后双指针一前一后去遍历,每一次都定义一个变量g(随意命名),如果符合 𝑥−𝑦 ≤ 𝑘则g += x,然后每一次都与res比较去更新res的值
代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 5;
int a[N];
int n,k,res = a[0];
int main()
{
cin >> n >> k;
for(int i=0;i<n;i++){
cin >> a[i];
}
sort(a+0,a+n);
// for(int i=0;i<n;i++){
// cout << a[i] << " ";
// }
// cout << endl;
for(int i=1;i<n;i++){
int g = 0;
for(int j=0;j<=i;j++){
if(a[i] - a[j] <= k) g += a[j];
}
res = max(res,g);
}
cout << res << endl;
return 0;
}
加油