1 条题解

  • 0
    @ 2025-10-8 17:01:36
    #include<bits/stdc++.h> 
    using namespace std;
    const int N=110000;
    const double eps=1e-6;
    double a[N],sum;
    int n,k;
    bool check(double x)
    {
        double s=0;
        for(int i=2;i<n;i++)
        {
            if(s>0)s+=a[i];
            else   s=a[i];
            if(sum-s<=0)return 1;
        }
        return 0;
    }
    int main()
    {
        scanf("%d",&n);
        double l=0,r=0,ans;
        for(int i=1;i<=n;i++)scanf("%lf",&a[i]),r+=a[i];
        sum=r;
        while(l<r)
        {
            double mid=(l+r)/2;
            for(int i=2;i<n;++i)a[i]-=mid;
            sum-=mid*n;
            if(check(mid))r=mid-eps,ans=mid;
            else          l=mid+eps;
            for(int i=2;i<n;++i)a[i]+=mid;
            sum+=mid*n;
        }
        printf("%.3lf",ans);
        return 0;
    }
    
    • 1

    *【二分】平均值最小[USACO14MAR]Sabotage

    信息

    ID
    2605
    时间
    1000ms
    内存
    128MiB
    难度
    3
    标签
    递交数
    72
    已通过
    37
    上传者