P2115 [USACO14MAR]破坏（二分答案）

给定一串数，问删除中间一段，剩下的平均数最小是多少；

不容易想到这是个二分。

$solution：$

来手玩一点式子：

首先很容易想到一个前缀和$sum_i $表示i到1的前缀和，这样就能很容易地O（1）查询区间和/差

二分一个mid，作为最小的平均数。

假设删去区间为l～r（lr都删）

平均数等于：

$ave={sum_{i-1} + sum_{n-j} }/{n-(j-i+1)}$

于是，这里就就有了单调性：

$mid leq ave$

稍微变形一下，就得到

$sum_n-sum_j+sum_{i-1} leq mid*n-mid*j+mid*(i-1)$

即

$(sum_n-mid*n) geq (sum_j-mid*j) - (sum_{i-1}-mid*(i-1)  $

令$sum_i-i*mid$=$C_i$

则只需要判断

$C_n geq C_j - C_{i-1} $

就能判断二分边界了。

复杂度$O（n）$

稍微注意下边界，就能A掉了。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+233;
double sum[maxn];
int n;
double c[maxn];
double maxx[maxn];
double minn[maxn];
bool check(double x)
{
    for(int i=0;i<=n;i++)
    {
        c[i]=sum[i]-i*x;
    }
    minn[1]=c[1];
    for(int i=2;i<=n;i++)
    {
        minn[i]=min(c[i],minn[i-1]);
    }
    maxx[n-1]=c[n-1];
    for(int i=n-2;i>=1;i--)
    {
        maxx[i]=max(c[i],maxx[i+1]);
    }
    for(int i=2;i<n;i++)
    {
        if(maxx[i]-minn[i-1]>c[n])
        return 1;
    }
    return 0;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        double x;
        scanf("%lf",&x);
        sum[i]=sum[i-1]+x;
    }
    double l=0,r=1e4+233;
    while((r-l)>0.000000001)
    {
        double mid=(l+r)/2;
        if(check(mid)==0)
        l=mid;
        else
        r=mid;
    }
    printf("%.3lf",l);
    return 0;
}

（完）