题目背景
Facer 误闯入禁地，学会了魔法。

题目描述
Facer 闯入禁地之后，遇到了对手。

具体来说，Facer 魔法是一串数字。

但是 Facer 能力有限，这串数字只能从给定的 n 个数中选择，能产生的魔法值为选择出的这些数字的平均数。

他的对手不会像 Facer 这样的强大的魔法，但是他会克制招数，即从 Facer 选出的数字中找出中位数，便是他的魔法值。

求 Facer 最多能克制对方多少点魔法。

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

输入格式
第一行一个正整数 n。

第二行 n 个数如题。

输出格式
Facer 能克制对方多少魔法值，精确到两位小数。

首先我们阔以证明一个结论，选择奇数个一定比选择偶数个更优，比如你选了偶数个，我们把中间两个较大的数去掉，对平均数的影响必然更小（阔以证明），之后呢由于这题的数据范围决定了这个应该是个nlog的算法，所以我们阔以枚举中位数，之后用三分求最大值（因为这个题满足单峰函数的性质。
水题

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
int n;
int a[100005];
int sum[100005];
double ans;
double max_1(double x,double y){
   return x>y?x:y;}
inline int read(){
   
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
   if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){
   x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
inline void solve(int tmp){
   //单峰函数，三分算法天下第一 
	int zhongwei=a[tmp];
	int l=1,r=min(tmp-1,n-tmp);
	int mid,midr;
	int maxx1,maxx2;
	double anss=0;
	while(r>l){
   
		mid=(l*2+r)/3;
		midr=(l+r*2+2)/3;
		maxx1=sum[n]-sum[n-mid]+sum[tmp]-sum[tmp-mid-1];
		maxx2=sum[n]-sum[n-midr]+sum[tmp]-sum[tmp-midr-1];
		if(maxx1*(2*midr+1)<maxx2*(2*mid+1)) l=mid+1;
		else r=midr-1;
	} 
	anss=(double)1.0*(sum[n]-sum[n-l]+sum[tmp]-sum[tmp-l-1])/(l*2+1);
	ans=max_1(ans,anss-(double)(1.0)*zhongwei);
}
int main(){
   
	n=read();
	sum[0]=0; 
	for(int i=1;i<=n;i++) a[i]=read();
	sort(a+1,a+n+1);//排序么么哒 
	for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];
	for(int i=2;i<=n-1;i++)solve(i);//枚举中位数 选择奇数个数字 
	printf("%.2lf",ans);
	return 0;
}