Codeforces Round #464 (Div. 2)-E-Maximize!（二分or三分）

题意：给你一个初始为空的集合，每次有两种操作：

（1）将集合中添加一个新数，这个数保证不小于集合中任何一个数

（2）你选择已有集合的一个子集，使得该集合最大的元素-（该集合所有元素的平均值）的值最大

题解：首先一个结论是最大的呢个数一定要加上，因为其他数都比它小，所以会减弱它对平均值的贡献的基础上又能保证最大值尽可能大，之后你要知道，你选的这个集合除了最大的呢个数，其他元素一定是连续的，如果你隔一个小的去拿大的呢不是脑子有病吗？，所以我们可以用sum求一下前缀和，然后我们在纸上随便找几个数算算就会发现，随着你挑选的子集的元素数值越来越大，其对平均值的影响也越来越大，但是也有可能所有的数值都很小，因此这个趋势要么是递减，要么是先递减后递增，因此我们可以二分找转折点或者三分即可。

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define ll long long 
ll q,t,len,a[500005],ans,sum[500005];
double work(int x)
{
	return (double)(a[len]+sum[x])/(double)(x+1);
}
int main(void)
{
	scanf("%lld",&q);
	while(q--)
	{
		scanf("%lld",&t);
		if(t==1)
		{
			scanf("%lld",&a[++len]);
			sum[len]=sum[len-1]+a[len];
		}
		else
		{
			ll l=0,r=len-1;
			while(l+1<r)
			{
				ll mid=(l+r)/2;
				if((a[len]+sum[mid])*(mid+2)>(a[len]+sum[mid+1])*(mid+1))
					l=mid;
				else
					r=mid;
			}
			printf("%.7f\n",(double)a[len]-work(r));
		}
	}
	return 0;
}