【积累】想不到可以二分..

洛谷P2115

题目描述

给一组长度为 \(N\;(3\leq N\leq100000)\) 的整数数组 \(a\;(1\leq a_i\leq 10000)\)，要求必须删去一个连续区间 \([l,r]\) ，且满足 \((2\leq l\leq r\leq n-1)\) ，求剩余区间的平均值的最小值。

输入格式

第 \(1\) 行：一个整数 \(N\;(3\leq N\leq100000)\) 。

第 \(2\) 到第 \(N+1\) 行：第 \(i+1\) 行包含一个整数 \(a_i\;(1\leq a_i\leq 10000)\) 。

输出格式

第 \(1\) 行：一个实数，表示平均值的最小值，四舍五入保留三维小数。

样例

输入：

5
5
1
7
8
2

输出：

2.667

题解

对于一个满足题意的ans，有：

所以二分ans，在check函数中判断即可。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
const double eps=1e-6;

int a,n;
double sum[maxn];
bool eql(double a,double b){return fabs(a-b)<1e-9;}
bool check(double x)
{
    double mi=sum[1]-x;
    for(int i=2;i<n;i++)
    {
        if(sum[n]-sum[i]-x*(n-i)+mi<0||eql(sum[n]-sum[i]-x*(n-i)+mi,0))return 1;
        mi=min(mi,sum[i]-x*i);
    }
    return 0;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a),sum[i]=sum[i-1]+a;
    double l=1,r=100000,mid,ans;
    while(l<r||eql(l,r))
    {
        mid=(l+r)/2;
        if(check(mid))ans=mid,r=mid-eps;
        else l=mid+eps;
    }
    printf("%.3lf\n",ans);
}