【传送门：BZOJ3477】
简要题意：
约翰的牧场里有N 台机器，第i 台机器的工作能力为Ai。保罗阴谋破坏一些机器，使得约翰的 工作效率变低。保罗可以任意选取一段编号连续的机器，使它们停止工作。但这样的破坏只能搞一次， 而且保罗无法破坏第一台或最后一台机器。请问他该破坏哪些机器才能让剩下机器的工作效率的平均 数最小？为了显示存在感，保罗至少必须破坏一台机器。
输入格式：
• 第一行：单个整数N，3 ≤ N ≤ 10^5
• 第二行到第N + 1 行：第i + 1 行有一个整数Ai，1 ≤ Ai ≤ 10000
输出格式：
• 单个浮点数：表示保尔破坏机器之后约翰的最低平均工作效率，以四舍五入的方式保留三位小数
样例输入：
5
5
1
7
8
2
样例输出：
2.667
样例解释：
移去7 和8，留下5，1 和2，平均数是8/3
题解：
二分最小平均数，用求最大连续子段和的方法来判断是否成立（精度问题卡了超久）
温馨提示：一串数中，我们假设p为这串数的平均数，将每个数都减去p后得到的值相加等于0
参考代码：
#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; double a[110000];int n; double s; bool check(double x) { double mx=a[2]-x; double pre=0.0; for(int i=3;i<n;i++) { pre+=a[i]-x; if(pre>mx) mx=pre; if(pre<0.0) pre=0.0; } return s-(double(n)*x)-mx<0; } int main() { scanf("%d",&n);s=0.0; for(int i=1;i<=n;i++) { scanf("%lf",&a[i]); s+=a[i]; } double l=0.0,r=s; double ans=0.0; while(l<=r) { double mid=(l+r)*0.5; if(check(mid)==true) { ans=mid; r=mid-0.00001; } else l=mid+0.00001; } printf("%.3lf ",ans); return 0; }