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

檀溪的小窝 / 2024-09-27 / 原文

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

~~谁家全排列写错了导致暴力分都没拿到啊！~~

通过数据范围倒推时间复杂度。

$n \le 10^5$，一眼 $O(n\log n)$。

再结合暴力打表，很容易发现规律：

当 $a$ 从小到大排列时，取到最大值；当 $a$ 从大到小排列时，取到最小值。

感性理解一下，以最小值为例。欲取到最小值，即要使得 $b$ 中的 $0$ 尽量多。若已知前 $i $ 项的排列方式，必然选择之后的最大值，从而使得 $a_{i + 1} > \bar{b_i}$

接下来以最小值为例对结论进行证明：

记从大到小排序后新序列的第 $i$ 项为 $a_i$，前 $i$ 项的平均值为 $\bar{b_i}$。

先考虑两个排序后的相邻项 $a_i, a_{i + 1}$，若交换这两项的顺序：

$b_i = b_{i + 1} = 0$，交换不会产生任何影响。
$b_i = 0, b_{i + 1} = m$，则有 $\bar{b_{i - 1}}>a_i\ge a_{i+1}$。交换后 $b_i' = b_i = 0$，则 $\bar{b_i}' = \bar{b_i}\le a_{i + 1} \le a_i$，$b_{i + 1}' = m$，结果不变。
$b_i = m, b_{i + 1} = 0$，则有 $\bar{b_{i - 1}} \le a_i,\;\bar{b_i} > a_{i + 1}$。记交换后的序列变为 $b'$：
1. 若 $a_{i + 1} < \bar{b_{i - 1}}$：$b_{i}' = 0$，则 $\bar{b_{i}}' = \bar{b_{i - 1}} \le a_i$，则 $b_{i - 1}' = m$，对最终平均值无影响。
2. 若 $a_{i + 1}\ge\bar{b_{i - 1}}$：$b_i' = m$，则 $\bar{b_i}' = \bar{b_i}$，不论 $b_{i + 1}$ 取 $0$ 还是 $m$，最终结果都不会变小。
$b_i = b_{i + 1} = m$，则有 $a_i\ge\bar{b_{i - 1}},\;a_{i + 1}\ge\bar{b_i}$。由于 $b_{i - 1}\le m$，所以 $\bar{b_i} \ge \bar{b_{i - 1}}$，所以 $a_{i + 1} \ge \bar{b_{i - 1}}$，$b_i' = m$，$\bar{b_{i}}' = \bar{b_i}$，$a_i\ge a_{i+1}\ge\bar{b_i} = \bar{b_i}'$，则 $b_{i + 1}' = m$，最终结果不变。

因此对两个相邻项的交换不会使得答案变小。

而对两个非相邻项则可以通过多次相邻项的交换来达到（类似于冒泡排序）。

因此当 $a$ 从大到小排列时，取到最小值。

最大值同理。

于是得到了我见过的最简单的蓝题代码（这题真的有蓝吗）：

#include<bits/stdc++.h>
#define MAXN 100010
using namespace std;
int n, m;
int a[MAXN];
double max_s, min_s;
int main(){
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; i++) scanf("%d",&a[i]);
    sort(a + 1, a + n + 1);
    for(int i = 2; i <= n; i++){
        double ave = max_s / (i - 1);
        if(ave > a[i]) max_s += 0;
        else max_s += m;
    }
    for(int i = n - 1; i >= 1; i--){
        double ave = min_s / (n - i);
        if(ave > a[i]) min_s += 0;
        else min_s += m;
    }
    printf("%.2f %.2f\n",max_s / n, min_s / n);
    return 0;
}