codeforce626 E. Simple Skewness 二分

codeforce626 E. Simple Skewness

均值-中位数 最大的子集

枚举中值，二分区间大小

要使 均值-中位数 最大，所以最大化均值，即从最后取最大的L个数，从中位数前取相邻的L个数

若区间扩大均值扩大则扩大，否则缩小

#include<bits/stdc++.h>
using namespace std;
const int MAX=2e5+5;
int a[MAX],n;
long long sum[MAX];
int main()
{
    while(~scanf("%d",&n))
    {
        memset(sum,0,sizeof(sum));
        int L=0,pos=1;double ans=-1e6;
        for(int i=1;i<=n;++i) scanf("%d",&a[i]);
        sort(a+1,a+n+1);
        for(int i=1;i<=n;++i) sum[i]+=sum[i-1]+a[i];
        for(int i=1;i<=n;++i)
        {
            int l=1,r=min(n-i,i-1),mid,len=0;
            while(l<=r)
            {
                mid=(l+r)>>1;
                double tmp1=1.0*(sum[n]-sum[n-mid]+sum[i]-sum[i-mid-1])/(2.0*mid+1);
                double tmp2=1.0*(sum[n]-sum[n-mid+1]+sum[i]-sum[i-mid])/(2.0*mid-1);
                if(tmp1>tmp2) l=mid+1,len=mid;
                else r=mid-1;
            }
            double ans_=1.0*(sum[n]-sum[n-len]+sum[i]-sum[i-len-1])/(2.0*len+1)-a[i];
            if(ans_>ans)
            {
                ans=ans_;
                L=len;
                pos=i;
            }
        }
        printf("%d\n",L*2+1);
        for(int i=pos-L;i<=pos;++i) printf("%d ",a[i]);
        for(int i=n-L+1;i<=n;++i) printf("%d ",a[i]);
        printf("\n");
    }
    return 0;
}