Description
FJ 的死对头，FP，现在决定了去破坏FJ 的挤奶设备！
这个挤奶设备由一行N（3 <= N<= 100, 000）个挤奶机器，其中第i 个机器生产Mi 单位的牛奶（1<= Mi <= 10, 000）。FP 计划将机器连续的一块断开——从第i 个机器到第j 个机器（2<= i<= j<= N-1）；注意第一个和最后一个机器FJ 并不想要断开，因为这会让这次事件太容易被发现。FP 的目标是让剩下的机器的牛奶平均产量最小。FP 打算移去至少一台机器，即使对他来说不进行破坏更好。
幸运的是，FJ 已获悉FP 的邪恶计划，并且他想知道如果计划成功他的挤奶设备会被破坏成什么样。请帮助FJ 找到，如果FP 成功，最小的剩下挤奶机器的平均生产量。
第一行：整数N。
第2 至N + 1 行：第i + 1 行包含Mi。
Output
输出单独一行一个整数——FP 能获得的最小的可能的平均数，四舍五入到小数点后3 位数字，小数点后三位数字都要输出。
5
5
1
7
8
2
Sample Output
2.667
样例解释：
最佳方案是移除7 和8，留下5; 1 以及2，使得平均值为8/3。
Data Constraint
对于14% 的数据，有N<=10。
对于49% 的数据，有N <=1000。
思路
只能删除一段数字，正常的o^2的会超时，所以考虑其他想法。
看到求最小值，就想二分如何：
假设当前切断了i——j，sum为前缀和，那么平均值为(sum[n]-sum[j]+sum[i-1])/(n-j+(i-1))，我们二分一个期望平均值x 即答案，很明显，如果当前的x是满足的，那么所有可能的平均值应该>=x,即
(sum[n]-sum[j]+sum[i-1])/(n-j+(i-1))>=x
(sum[n]-nx)-(sun[j]-jx)+(sum[i-1]-(i-1)x)>=0
设p[i]=sum[i]-ix
就可以化简成 p[j]-p[i-1]<=p[n]
#include<cstdio>
using namespace std;
int a[120000],n,m,x[110000];
double sum,l,r;
double pd(double t)
{double p[110000],f[110000];for (int i=1;i<=n;i++)p[i]=x[i]-i*t;f[1]=p[1];for (int i=2;i<=n;i++)if (p[i]<f[i-1]) f[i]=p[i];else f[i]=f[i-1];double ma=-10000;for (int i=n-1;i>=2;i--){if (p[i]>ma) ma=p[i];if (ma-f[i-1]>p[n]) return 0;}return 1;
}
int main()
{scanf("%d",&n);for (int i=1;i<=n;i++){scanf("%d",&a[i]);x[i]=x[i-1]+a[i];}l=0;r=10000;while (l<r){if (r-l<0.0001) break;double mid=(l+r)/2;if (pd(mid)) l=mid;else r=mid;}printf("%.3lf",l);
}