思路
原题是这个：【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;
}