自动搬运

查看原文

来自洛谷，原作者为

	chen_zhe Aya 敲可爱的~

搬运于2025-08-24 21:16:30，当前版本为作者最后更新于2024-07-03 18:56:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

如果宝箱的价值是杂乱无章的（例如：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)$ 呢（即：排序算法的时间复杂度占程序的主要部分）？