题解 P2797 【Facer的魔法】
XG_Zepto
2018-05-29 17:58:38
## 思路
推广个人博客[【Codeforces 626E】 Simple Skewness / 题解](https://www.xgzepto.cn/post/codeforces-626e)
原题是这个：[【Codeforces 626E】 Simple Skewness](http://codeforces.com/problemset/problem/626/E)
题意：从数列里选出若干个数，使得他们的平均数减中位数最大。
这个问题有三个性质：
- 答案一定是非零数。因为你只选择一个数的时候，答案为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;
}
```