传送门biu~ 二分答案x，表示删数后序列的平均数为x。让原序列每个数减去x，并删去最大子段，判断剩下的数的和是否小于等于0，如果小于等于0证明平均数小于等于x。
#include<bits/stdc++.h> using namespace std; const double eps=0.00001; int n,a[100005],sum; double b[100005],tot; inline bool check(double x){ tot=sum-x*n; double now=0,Max=0; for(int i=2;i<n;++i){ b[i]=a[i]-x; if(now+b[i]>0){ now+=b[i]; Max=max(Max,now); } else now=0; } if(Max==0){ Max=-1e9; for(int i=2;i<n;++i) Max=max(Max,b[i]); } return (tot-Max)<=0; } inline double binary_search(){ double l=0,r=sum; while(r-l>eps){ double mid=(l+r)/2; if(check(mid)) r=mid; else l=mid; } return r; } int main(){ scanf("%d",&n); for(int i=1;i<=n;++i) scanf("%d",&a[i]),sum+=a[i]; printf("%.3lf\n",binary_search()); return 0; }