hello.

题解 P2797 【Facer的魔法】

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;
}