Description：

有一个序列，删除一个区间使得剩余的数的平均值最小。

$1\le n \le 100000$

Solution：

$01$ 分数规划，设二分出来的值是 $x$ ，那么如果 $\frac{sum[n]-(sum[i]-sum[j])}{n-(i-j)}\le x$ ，就把右端点往左调，乘过去移项得： $(sum[n]-n\times x)-(sum[i]-i\times x)+(sum[j]-j\times x)\le 0$ ，于是维护 $sum[j]-j\times x$ 的最小值就可以判断了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n;

#define MAXN 100010

double val[MAXN];

double sum[MAXN];

bool check(double x)

{

	double presum = 10000000000;

	for(int i = 1;i < n;++i)

	{

		if(sum[n] - n * x - (sum[i] - i * x) + presum <= 0)

		{

			return true;

		}

		presum = min(presum,sum[i] - i * x);

	}

	return false;

}

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%lf",&val[i]);

	for(int i = 1;i <= n;++i)sum[i] = sum[i - 1] + val[i];

	double l = 0,r = 10000000000,mid;

	while(r - l > 1e-6)

	{

		mid = (l + r) / 2;

		if(check(mid))r = mid;

		else l = mid;

	}

	printf("%.3lf\n",l);

	return 0;

}