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+;

double sum[maxn];

int n;

double c[maxn];

double maxx[maxn];

double minn[maxn];

bool check(double x)

{

    for(int i=;i<=n;i++)

    {

        c[i]=sum[i]-i*x;

    }

    minn[]=c[];

    for(int i=;i<=n;i++)

    {

        minn[i]=min(c[i],minn[i-]);

    }

    maxx[n-]=c[n-];

    for(int i=n-;i>=;i--)

    {

        maxx[i]=max(c[i],maxx[i+]);

    }

    for(int i=;i<n;i++)

    {

        if(maxx[i]-minn[i-]>c[n])

        return ;

    }

    return ;

}

int main()

{

    scanf("%d",&n);

    for(int i=;i<=n;i++)

    {

        double x;

        scanf("%lf",&x);

        sum[i]=sum[i-]+x;

    }

    double l=,r=1e4+;

    while((r-l)>0.000000001)

    {

        double mid=(l+r)/;

        if(check(mid)==)

        l=mid;

        else

        r=mid;

    }

    printf("%.3lf",l);

    return ;

}

（完）

巴特西

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

最新文章

热门文章