给出一个长为n的正整数序列(n<=1e5),要求选出一个非空前缀和一个非空后缀(这两段不能够加起来组成整个序列),使得这个前缀和后缀中的所有数字一起求平均数的结果最小
最大/最小化平均数的题目一眼就是二分这个平均数,原序列每个数字减去平均数,转化为和大于0/和小于0的判断.求求前缀和没了. 咸鱼选手这都1A不了QAQ
#include<cstdio> const int maxn=100005; int a[maxn]; double sum[maxn]; double min_suffix[maxn]; int n; bool check(double ans){ for(int i=1;i<=n;++i)sum[i]=a[i]-ans; for(int i=2;i<=n;++i)sum[i]+=sum[i-1]; for(int i=n;i>=1;--i)min_suffix[i]=sum[n]-sum[i-1]; for(int i=n-1;i>=1;--i)if(min_suffix[i+1]<min_suffix[i])min_suffix[i]=min_suffix[i+1]; for(int i=1;i<=n-2;++i)if(sum[i]+min_suffix[i+2]<-(1e-6))return true; return false; } int main(){ scanf("%d",&n); for(int i=1;i<=n;++i)scanf("%d",a+i); double lo=0,hi=1e6; for(int i=1;i<=50;++i){ double mid=(lo+hi)/2.0; if(check(mid))hi=mid; else lo=mid; } printf("%.3f\n",lo); return 0; }转载于:https://www.cnblogs.com/liu-runda/p/7531975.html
相关资源：数据结构—成绩单生成器