bzoj3477[Usaco2014 Mar]Sabotage

题意

给出一个长为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;

}

巴特西

bzoj3477[Usaco2014 Mar]Sabotage

题意

分析

最新文章

热门文章