[Codeforces 626E]Simple Skewness

這題乍看之下有點麻煩，要求平均數、中位數，還要考慮所有子集合而不是子序列

但，有時候，看起來條件越寬鬆的問題，越容易枚舉
因為考慮的是子集合，序列中元素的先後順序就不重要了，乾脆先排序一下

為了方便說明，令$S_{i}$為排序後序列的第$i$個元素

我們會需要求平均數-中位數的最大值
如果要枚舉，觀察一下枚舉甚麼最適合 (選項：子集合頭、平均數、中位數)
就是中位數啦
這樣就可以對每個中位數，左邊選$k$個數字，右邊也選$k$個數字 (注意此時序列已經排序完成)，盡量讓平均最大
假設現在中位數枚舉到$S_{i}$，我們來討論看看最佳的選數字方法是甚麼
如果$k=1$，那麼左邊選$S_{i-1}$，右邊選$S_{N}$，一定是最佳的
如果$k=k$，那麼左邊選$S_{i-k}\sim S_{i-1}$，右邊選$S_{N-k}\sim S_{N}$，一定是最佳的

可以發現，當$k$決定了，就可以很輕易地給出最佳數字選擇方案
當$k$慢慢增加時，最佳數字選擇方案所得到的平均值會有甚麼變化呢？

可以發現，平均值會先升後降

因此可以套用三分搜來尋找這個$k$讓平均值最大，注意$k$可以$=0$
三分搜的詳情請參考code

至於平均值的計算
因為最佳的選數字方法會選擇連續的兩段數字，可以考慮預處理前綴和，然後兩段連續數字和就可以用前綴和相減的方式求出，相加之後再除以總數就是平均值

枚舉$i$，三分搜找出最佳$k$並更新答案
這樣就完成了嗎？
好像還沒耶

中位數有可能是中間兩數的平均
因此需要再枚舉一次相鄰兩數的平均當中位數的情況 (這時相鄰兩數可以合併作一個權重2的數字看待)
也符合上述的三分搜單調性，依照上述做法再做一次就好

時間複雜度：$O(N\log N)$

code:

#include<cstdio>
#include<cassert>
#include<algorithm>
using namespace std;
typedef long long LL;
int N;
LL S[200001],SUM[200001];
double ANS_BEST;
int ANS_L1,ANS_L2,ANS_R1,ANS_R2;
void Update(const double &ans_best,const int ans_l1,const int ans_l2,const int ans_r1,const int ans_r2)
{
    if(ans_best<=ANS_BEST)return;
    ANS_BEST=ans_best,ANS_L1=ans_l1,ANS_L2=ans_l2,ANS_R1=ans_r1,ANS_R2=ans_r2;
}
double OddAns(const int mid,const int k)
{
    return (double)((SUM[mid]-SUM[mid-k-1])+(SUM[N]-SUM[N-k]))/(k*2+1)-S[mid];
}
double EvenAns(const int mid,const int k)
{
    return (double)((SUM[mid+1]-SUM[mid-k-1])+(SUM[N]-SUM[N-k]))/(k*2+2)-0.5*(S[mid]+S[mid+1]);
}
void Solve(vector<int>&ans)
{
    ANS_BEST=-1.0;
    sort(S+1,S+N+1);
    for(int i=1;i<=N;i++)SUM[i]=SUM[i-1]+S[i];
    for(int i=1;i<=N;i++)
    {
        int l=0,r=min(i-1,N-i);
        while(r-l>=3)//三分搜
        {
            const int ml=(l*2+r)/3,mr=(l+r*2)/3;
            if(OddAns(i,ml)<OddAns(i,mr))l=ml;
            else r=mr;
        }
        for(int k=l;k<=r;k++)assert(k>=0),Update(OddAns(i,k),i-k-1,i,N-k,N);
    }
    for(int i=1;i<N;i++)
    {
        int l=0,r=min(i-1,N-(i+1));
        while(r-l>=3)//三分搜
        {
            const int ml=(l*2+r)/3,mr=(l+r*2)/3;
            if(EvenAns(i,ml)<EvenAns(i,mr))l=ml;
            else r=mr;
        }
        for(int k=l;k<=r;k++)assert(k>=0),Update(EvenAns(i,k),i-k-1,i+1,N-k,N);
    }
    ans.clear();
    assert(ANS_L1<ANS_L2);
    for(int i=ANS_L1+1;i<=ANS_L2;i++)ans.push_back(S[i]);
    for(int i=ANS_R1+1;i<=ANS_R2;i++)ans.push_back(S[i]);
}
int main()
{
//    freopen("in.txt","r",stdin);
    while(scanf("%d",&N)==1)
    {
        for(int i=1;i<=N;i++)scanf("%I64d",&S[i]);
        vector<int>ans;
        Solve(ans);
        printf("%d\n",(int)ans.size());
        for(int i=0;i<(int)ans.size();i++)
        {
            if(i)putchar(' ');
            printf("%d",ans[i]);
        }
        puts("");
    }
    return 0;
}