洛谷 P2797 Facer的魔法解题报告 P2797 Facer的魔法

题意：给你n个数，你可以选若干个数，使得平均数减中位数最大

(n le 10^5)

原题CF626E

很容易想到枚举一个中位数，但是如果选取的数字的个数是偶数个该怎么办呢？

下面证明选取奇数个时一定可以作为答案

当选取一个数字时，答案为0，所以最优答案不可能小于0，这点很重要

现在，我们假设选取了(2k)个有序的数成为了答案

(A_0=frac{sum a}{2k})

拿掉一个(a_{k+1})后答案会变差吗

设拿掉一个(a_{k+1})后

(M_1=a_k,A_1=frac{sum a-a_{k+1}}{2k-1})

(Delta M=M_1-M_0=frac{a_k-a_{k+1}}{2})

(Delta A=frac{A_0-a_{k+1}}{2k-1})

现在要证(Delta A ge Delta M)

因为最优答案大于0，所以有

(2 imes A_0 ge a_k+a_{k+1})

继续证明

$Delta A ge Delta M $

(Rightarrow frac{A_0-a_{k+1}}{2k-1}+frac{a_{k+1}-a_k}{2} ge 0)

(Rightarrow frac{2A_0-2a_{k+1}+(2k-1)(a_{k+1}-a_k)}{(2k-1) imes 2} ge 0)

(Rightarrow a_k-a_{k+1} +(2k-1)(a_{k+1}-a_k) ge 0)

这一步用了上面的东西，并把正的分母去掉了

(Rightarrow 2 imes (k-1)(a_{k+1}-a_k) ge 0)

然而仅仅枚举中位数，就算我们贪心每次选大的数也需要(O(n^2))的时间啊

我们从枚举的中位数的左边第一位和右边最后一位一位一位的向左多选

因为选取的数字越来越小，所以平均数的增量肯定越来越小，其实这个不那么显然，但是证起来比较麻烦

而大家基本上可以理解理解啦

增量减少，值一定有一个峰顶，这是一个单峰函数，我们可以通过三分法找到这个峰顶

注意在整数域上三分要注意边界问题

我们可以这么写
(lmid=(l*2+r)/3,rmid=(l+r*2+2)/3)

Code:

#include <cstdio>
#include <algorithm>
const int N=1e5+10;
double ans=0;int a[N],f[N],n;
double max(double x,double y){return x>y?x:y;}
int min(int x,int y){return x<y?x:y;}
int F(int pos,int len)
{
    return f[pos]-f[pos-len-1]+f[n]-f[n-len];
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",a+i);
    std::sort(a+1,a+1+n);
    for(int i=1;i<=n;i++) f[i]=f[i-1]+a[i];
    for(int i=2;i<n;i++)
    {
        int l=1,r=min(i-1,n-i);
        while(l<r)
        {
            int ll=(l*2+r)/3,rr=(l+r*2+2)/3;
            if(F(i,ll)*(rr*2+1)<F(i,rr)*(ll*2+1))
                l=ll+1;
            else
                r=rr-1;
        }
        ans=max(ans,1.0*F(i,l)/(l*2+1)-1.0*a[i]);
    }
    printf("%.2lf
",ans);
    return 0;
}

2018.9.6

洛谷 P2797 Facer的魔法 解题报告 P2797 Facer的魔法