题解 P2797 【Facer的魔法】

XG_Zepto · 2018-05-29 17:58:38 · 题解

思路

推广个人博客【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 <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#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;i<n;i++){
        int l=1,r=min(n-i,i-1);
        while(l<r){
            ll s1=sum(i,mid)*(2*mid+3);
            ll s2=sum(i,mid+1)*(2*mid+1);
            //为了避免精度问题，用乘法代替除法比较大小。
            if (s1>s2){
                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;
}