codeforces 626E

我又诈尸了

题意：给一个数组，让你找一个子序列使得平均值减去中位数尽可能的大 n=2e5
首先易证 奇数长度不可能比偶数长度 劣
所以最终答案是奇数
假设中位数是确定的，那么我们对于不同的长度显然在左边和右边贪心选最大的
所以我们三分就行

这好像是我为数不多的几次写整数三分
妈的我明明都退役了还写你妈题呢
匿名函数都不会写了[卑]

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const int N = 2e5+5;
int n,a[N];db ans[N];ll pre[N];db ed;int id,len;
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++)pre[i]=pre[i-1]+a[i];
    if(n<=2) return 0*printf("1
%d
",a[1]);
    for(int i=2;i<=n-1;i++){
        auto s = [&](int len){ return pre[n]-pre[n-len]+pre[i]-pre[i-1-len]; };
        int l=1,r=min(i-1,n-i);
        while (l<r){
            int lm = (l+l+r)/3;
            int rm = (r+r+l+2)/3;
            ll s1 = s(lm);
            ll s2 = s(rm);
            if(s1*(rm*2+1)>=s2*(lm*2+1)){
                r=rm-1;
            }else{
                l=lm+1;
            }
        }
        ans[i]=1.0*s(l)/(2*l+1)-a[i];
        if(ans[i]>ed) {
            ed = ans[i], len = l, id = i;
//            cout<<ans[i]<<endl;
        }
    }
    cout<<len*2+1<<endl;
    if(len==0) return 0*(printf("%d
",a[1]));
    for(int i=id-1;i>id-1-len;i--)cout<<a[i]<<' ';
    cout<<a[id];
    for(int i=n;i>n-len;i--)cout<<' '<<a[i];
}