自动搬运

查看原文

来自洛谷，原作者为

	Code_星云 Code_quantum QAQ

搬运于2025-08-24 22:36:08，当前版本为作者最后更新于2023-07-17 20:00:27，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

又是一道 (๑•ᴗ•๑) 的贪心题。题解区的好多题解写的都不详细，在这里严谨证明一下。

首先通过分析样例或者猜测，是很容易得到结论的：若要取最大值，则将序列从小到大排序；否则从大到小排序。

证明：

首先证明取最大平均值时的正确性。我们使用邻项交换法。

假设现在在序列中存在 $a_i \leq a_{i+1}$，且此时从 $1$ 到 $i-1$ 的平均值为 $s$。此时分三种情况考虑。

1. $s \leq a_i \leq a_{i+1}$。

首先考虑不交换时的贡献。当枚举到 $i$ 时，所取得值总和会加上 $m$，此时平均值也会增大（或不变）。如果增加后的平均值小于等于 $a_{i+1}$，则答案还可以增大。

其次考虑交换 $i$ 和 $i + 1$ 两项。此时当枚举到第 $i$ 个数时（注意，不是枚举到 $a_i$ 时），总和仍会加上 $m$，而枚举到第 $i +1$ 个数时，因为 $a_i \leq a_{i+1}$，所以相对不交换时，答案增加的概率会减小。如果答案仍能增加，此时对后面的贡献与不交换时相同。

那不增加时呢？有同学可能会说，由于不交换时答案变大了，平均值也会变大，那么后面就相比交换时取值的概率减小了。事实上，如果存在这样一种情况，即假若交换时，在后面某位置 $j$ 又能再取一个 $m$ 时，此时所取的总值也仅仅是和不交换时相同，而在 $j$ 后面时，两方案贡献又相同了。

综上，此条件下，不交换不会劣化答案。

2. $a_i \leq s \leq a_{i+1}$

不交换时，在第 $i$ 个数是不能增加答案的，然后 $s$ 会减小到 $s'$，由于 $s' \leq s \leq a_{i+1}$，因此在第 $i+1$ 个数时能取到。

交换时，在第 $i$ 个数能取到，然后 $s$ 会增加到 $s''$，由于 $s'' \geq s \geq a_i$，因此在 $i + 1$ 是不能取到。此时两方案对后面的贡献都是一个 $m$。

综上，此情况下，不交换和交换答案贡献相同。

3. $a_i \leq a_{i+1} \leq s$

不交换时，$i$ 不能取到，$s$ 会减小到 $s'$，若 $s' \leq a_{i+1}$，则会增加 $m$；否则不变。

交换时，$i$ 不能取到，$s$ 仍会减小到 $s'$，若 $a_i < s' \leq a_{i+1}$，答案不如不交换时（此时仍可以用第 $1$ 种情况里面对那个疑问的回答来证明对后面影响的不劣化性）；其余情况与不交换时相同。

综上，不交换不会劣化答案。

可以用数学归纳法推到到整个序列。

对于求最小值时，也可以类比上面的证明方法，这里就省略了。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define int long long

const int N = 100005;
const double eps = 1e-14;
int n, m, sum = 0, a[N];
double avr = 0.0;

signed main(){
	scanf("%lld %lld", &n, &m);
	for(int i = 1; i <= n; i ++) scanf("%lld", &a[i]);
	sort(a + 1, a + n + 1);
	for(int i = 1; i <= n; i ++){
		if(a[i] * 1.0 - avr > eps || fabs(a[i] * 1.0 - avr) < eps) sum += m;
		avr = 1.0 * sum / (1.0 * i);
	}
	printf("%.2lf ", avr); sum = 0;
	for(int i = n; i >= 1; i --){
		if(a[i] * 1.0 - avr > eps || fabs(a[i] * 1.0 - avr) < eps) sum += m;
		avr = 1.0 * sum / (1.0 * (n - i + 1));
	}
	printf("%.2lf\n", avr);
	return 0;
}