CF1557A 题解

· · 题解

题意描述

## 数据规模 $1 \leqslant t \leqslant 10^3$，$2 \leqslant n \leqslant 10^5$，$-10^9 \leqslant a_i \leqslant 10^9

思路

通过手算，不难发现当将最大的数单独一组时，平均值最大

证明

假设 a 数组已经从小到大排列，即存在 a_1 \leqslant a_2 \leqslant \dots \leqslant a_{n-1} \leqslant a_n

引理1：平均值的大小 average 介于数列最大值和最小值之间，设 average 为数组 a 的平均值，则存在

a_1 \leqslant average \leqslant a_n

如果不将 a_n 单独一组，那么当前的 ans 一定可以表示为：

\dfrac{\sum_{i=1}^{n-1}a_i-\sum_{i=1}^{m}a_{x_i}}{n-m-1}+\dfrac{\sum_{i=1}^{m}a_{x_i}+a_n}{m+1}\;\;(0<m<n-1)

因为可能包含重复的元素，考虑当 a 数组由单个元素重复多次构成时，分组的状态就不会对 ans 产生影响，即 ans 是一个定值

所以就要证明：

\dfrac{\sum_{i=1}^{n-1}a_i}{n-1}+a_n\geqslant\dfrac{\sum_{i=1}^{n-1}a_i-\sum_{i=1}^{m}a_{x_i}}{n-m-1}+\dfrac{\sum_{i=1}^{m}a_{x_i}+a_n}{m+1}

移项后，得：

a_n\geqslant\dfrac{\sum_{i=1}^{n-1}a_i-\sum_{i=1}^{m}a_{x_i}}{n-m-1}-\dfrac{\sum_{i=1}^{n-1}a_i}{n-1}+\dfrac{\sum_{i=1}^{m}a_{x_i}+a_n}{m+1}

即：

a_n\geqslant\dfrac{\sum_{i=1}^{n-1}a_i}{n-m-1}-\dfrac{\sum_{i=1}^{n-1}a_i}{n-1}+\dfrac{\sum_{i=1}^{m}a_{x_i}}{m+1}-\dfrac{\sum_{i=1}^{m}a_{x_i}}{n-m-1}+\dfrac{a_n}{m+1}

合并同类项后，得：

a_n\geqslant\dfrac{m\sum_{i=1}^{n-1}a_i}{(n-1)(n-m-1)}+\dfrac{(n-2m-2)\sum_{i=1}^{m}a_{x_i}}{(m+1)(n-m-1)}+\dfrac{a_n}{m+1}

移项后，得：

\dfrac{ma_n}{m+1}\geqslant\dfrac{m\sum_{i=1}^{n-1}a_i}{(n-1)(n-m-1)}+\dfrac{(n-2m-2)\sum_{i=1}^{m}a_{x_i}}{(m+1)(n-m-1)}

两边同时乘 (m+1)，得：

ma_n\geqslant\dfrac{m(m+1)\sum_{i=1}^{n-1}a_i}{(n-1)(n-m-1)}+\dfrac{(n-2m-2)\sum_{i=1}^{m}a_{x_i}}{n-m-1}

通分后得：

ma_n\geqslant\dfrac{m(m+1)\sum_{i=1}^{n-1}a_i}{(n-1)(n-m-1)}+\dfrac{(n-1)(n-2m-2)\sum_{i=1}^{m}a_{x_i}}{(n-1)(n-m-1)}

合并后，得：

ma_n\geqslant\dfrac{m(m+1)\sum_{i=1}^{n-1}a_i+(n-1)(n-2m-2)\sum_{i=1}^{m}a_{x_i}}{(n-1)(n-m-1)}

两边同除 m 得：

a_n\geqslant\dfrac{m(m+1)\sum_{i=1}^{n-1}a_i+(n-1)(n-2m-2)\sum_{i=1}^{m}a_{x_i}}{m(n-1)(n-m-1)}

先分析一下分子上有多少个元素：

一共有 m(m+1)(n-1)+(n-1)(n-2m-2)m 个元素

也就是 m(n-1)(m+1)+m(n-1)(n-2m-2) 个

合并后，只有 m(n-1)(m-n-1) 个元素

而分母也为 m(n-1)(n-m-1)

所以相当于对分子求一个平均值 avg'

式子就化为：

a_n\geqslant avg'

而分子由 a_1,a_2,a_3,\dots,a_{n-1} 一共 n-1 种不同元素重复多次构成

则根据上文的引理1，可得：

a_1\leqslant avg' \leqslant a_{n-1}

又因为 a 数组已经排序，所以 a_n\geqslant a_{n-1}

即

a_n\geqslant avg'

证毕

附比赛AC代码：

P.S. printf 函数自动输出 double 时默认输出 6 位，而 cout 则会有神奇的四舍五入,且默认最大长度只有 4 位

#include<bits/stdc++.h>
using namespace std;
double ans1,ans2;
int t,n;
long long maxn,sum,x;
int main(){
    scanf("%d",&t);
    while(t--){
        sum=0;maxn=-1e10;
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%lld",&x);
            maxn=max(maxn,x);
            sum+=x;
        }
        sum-=maxn;
        ans1=sum*1.0/(n-1);
        printf("%f\n",ans1+maxn*1.0);
    }
}