题目
题解
做法1：
直接暴力枚举每个数是否被选出，计算平均数-中位数，并与当前答案进行比较。复杂度O(2^n)，能过60%的数据。
做法2：
将每个数排序后枚举中位数。
首先，取奇数个数一定更优。容易证明，如果取偶数个数，中位数与平均数相距一定更小。
其次，除中位数以外，数一定尽量往后取，这样中位数不变，平均数增大，才能使答案最大。所以，中位数确定以后，枚举中位数两边数的个数（数都靠后取），计算答案。计算过程可以用前缀和把复杂度降到O(1)。
总的复杂度O(n^2+nlogn+n)=O(n^2)，能过75%的数据。
满分做法：
还是排序后枚举中位数。
注意到题目后的一长段话，由于f(w,l)为关于l的单峰函数，可以用三分法找出最佳的l。复杂度O(nlogn+nlogn+n)=O(nlogn)，能过100%的数据。
代码
#include <stdio.h>
#include <algorithm>
#define N 100005
int n,a[N],b[N];
int min(int a,int b){return a<b?a:b;}
double calc(int i,int l) {//计算平均数-中位数
return (b[i]-b[i-l-]+b[n]-b[n-l])/(double)((l<<)+);
}
int tricalc(int i) {//三分，中位数下标为i
int l=,r=min(i-,n-i),p,q,t;//l,r为三分区间，p,q为两个点
while(l<r) {
t=(r-l)/;
p=l+t;q=r-t;
if(calc(i,p)>calc(i,q)) r=q-; else l=p+;
}
return l;
}
int main() {
double tmp,ans=0.0;
scanf("%d",&n);
for(int i=;i<=n;++i) scanf("%d",a+i);
std::sort(a+,a+n+);
for(int i=;i<=n;++i) b[i]=a[i]+b[i-];//前缀和
for(int i=;i<=n;++i) {
tmp=calc(i,tricalc(i))-a[i];//三分找出最佳l
if(tmp>ans) ans=tmp;
}
printf("%.2lf",ans);
return ;
}
偷看一眼代码
完结撒花+日常%czhou~~~