【Codeforces 626E】 Simple Skewness / 题解

【Codeforces 626E】 Simple Skewness / 题解

思路

原题是这个:【Codeforces 626E】 Simple Skewness

题意:从数列里选出若干个数,使得他们的平均数减中位数最大。

这个问题有三个性质:

  • 答案一定是非零数。因为你只选择一个数的时候,答案为0;
  • 选出的数一定为奇数个。我们可以通过这个方法来证明:

假设原来我们选了 $2k$ 个数,这些数升序排列是 $a_1$ ~ $a_{2k}$ ,我们现在去掉 $a_{k+1}$ 这个数,答案一定不会变劣。

设原来的平均数为 $ av $,平均数的增量为:$$ΔAverage=\frac{av*2k-a_{k+1}}{2k-1}-av $$

中位数的增量为:$$ΔMedian=a_k-\frac{a_k+a_{k+1}}{2}$$

整理得:$$ΔAverage – ΔMedian = \frac{2av+(2k-1)(a_{k+1}-a_k)-a_{k+1}}{2(2k-1)}$$

上式显然大于零,证毕。

  • 选定中位数后,向选定数列中添加新数字,一定是选择了两边可选的最大数。不断添加新数字,平均数的变化是先增后减的,所以我们可以通过二分找到它的峰值。

结合以上三点,算法就非常地显然了:枚举每一个中位数,然后二分找到对应的平均数的最大值,更新答案。

代码

用VS写的,提交的时候要记得注释掉第一个库。

    // Facer's Magic.cpp: 定义控制台应用程序的入口点。
    // XG_Zepto, 5/25/2018
    // All rights reserved.
    #include "stdafx.h"
    #include 
    #include 
    #include 
    #include 
    #include 
    #define mid (l+(r-l)/2)
    #define ll long long
    #define maxn 1000005 
    ll s[maxn],a[maxn];
    int n;
    double ans;
    using namespace std;
    ll sum(int x,int l){
        return s[n]-s[n-l]+s[x]-s[x-l-1];
    }
    int main(){
        ios::sync_with_stdio(false);
        cin>>n;
        for (int i=1;i<=n;i++)
            cin>>a[i];
        sort(a+1,a+1+n);
        for (int i=1;i<=n;i++)
            s[i]=s[i-1]+a[i];
        for (int i=2;is2){
                    r=mid;
                }
                else{
                    l=mid+1;
                    if (s1==s2) break;
                }
            }
            if (1.0*sum(i,l)/(2*l+1)-a[i]>ans)
                ans=1.0*sum(i,l)/(2*l+1)-a[i];
        }
        printf("%.2f",ans);
        //记得保留两位小数
        return 0;
    }