4629: 【GESP2406四级】宝箱

内存限制：64 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：1 解决：1

题目描述

⼩杨发现了$n$ 个宝箱，其中第$i$ 个宝箱的价值是$a_i$ 。
小杨可以选择一些宝箱放入背包并带走，但是小杨的背包比较特殊，假设小杨选择的宝箱中最大价值为$x$ ，最小价值为$y$ ，小杨需要保证$x-y\le k$ ，否则小杨的背包会损坏。
小杨想知道背包不损坏的情况下，自己能够带走宝箱的总价值最大是多少。

输入

第一行包含两个正整数$n,k$ ，含义如题面所示。
第二行包含$n$ 个正整数$a_1,a_2,...,a_n$ ，代表宝箱的价值。

输出

输出一个整数，代表带走宝箱的最大总价值。

样例输入 复制 

5 1
1 2 3 1 2

样例输出 复制 

7

提示

#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";
}

来源/分类

提交提交记录统计露一手!