【Codeforces 8VC Venture Cup 2016 - Elimination Round 】E Simple Skewness

  考场上已经想到这题的做法了...然而写了个每次只移动一位找极值点的做法，不知道为什么是错的。半夜打比赛智商折半用。

  首先结果一定是一个长度为奇数的序列。因为如果是一个偶数的序列，那么把那个较大的中位数拿走，中位数的值减少量一定多于平均值减少量。

  然后考虑以i为中位数，长度为2L+1的序列，显然选择最大个L的数和小于等于ai的最大的L个数是最好的。显然结果关于L是个单峰函数，三分求之即可。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn=200010;

int a[maxn];
LL sum[maxn];
int n;
int ansm,ansl;
double ansv;

double f(int mid,int len)
{
	double res=0;
	res=sum[n]-sum[n-len]+sum[mid]-sum[mid-len-1];
	res/=(double)(len*2+1);
	res-=a[mid];
	return res;
}

int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	sort(a+1,a+1+n);
	for (int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];
	ansv=-1;
	for (int i=1;i<=n;i++)
	{
		int l=0,r=min(i-1,n-i);
		while (r-l>2)
		{
			int m1=l+(r-l)/3,m2=l+2*((r-l)/3);
			if (f(i,m1)<f(i,m2)) l=m1;else r=m2;
		}
		for (int j=l;j<=r;j++)
		{
			double res=f(i,j);
			if (res>ansv) ansv=res,ansm=i,ansl=j;
		}
	}
	printf("%d\n",ansl*2+1);
	for (int i=ansm-ansl;i<=ansm;i++) printf("%d ",a[i]);
	for (int i=n-ansl+1;i<=n;i++) printf("%d ",a[i]);
	printf("\n");
	return 0;
}