宝箱

chen_zhe · 2024-07-03 18:56:23 · 题解

欢迎报名洛谷网校，期待和大家一起进步！

:::align{center} :::

如果宝箱的价值是杂乱无章的（例如：6 8 10 7 3 5），那么问题会很难处理。如果我们将宝箱的价值进行排序，那么问题会变得轻松不少（例如：3 5 6 7 8 10）。

我们先将读入的 a_1,a_2,\dots,a_n 进行从小到大的排序。接着我们思考小杨如何能够选择宝箱。我们不妨枚举，小杨现在拿的宝箱 i 是价值最大的宝箱。那么小杨肯定要接着拿一些价值更小的宝箱。因此我们要枚举 j，j 一开始为 i，根据 a_j 从大到小的顺序去逐一选择这些宝箱，直到 a_i-a_j>k 为止。接着，我们将这些宝箱的价值与当前的最大值做比较，更新答案。

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];
    }
    ans = max(ans, sum);
}

思考：这个做法的时间复杂度为 O(n^2)。如何将其优化为 O(n \log n) 呢（即：排序算法的时间复杂度占程序的主要部分）？