P8113 [Cnoi2021] 自我主义的平衡者 题解

· · 题解

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

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

证明：

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

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

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

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

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

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

  1. 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。

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

  1. 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;
}