题解 P2115 【[USACO14MAR]破坏Sabotage】

XY_ATOE · 2017-10-13 09:34:48 · 题解

这个题是二分。假设s[i]表示m[i]的前缀和数组。假设去掉i,j这一部分机器则其余机器的平均产奶量可以表示为(s[n]-s[j]+s[i-1])/(n-j+i-1)。假设最小值为k，则有(s[n]-s[j]+s[i-1])/(n-j+i-1)>=k，显然可以二分，可得s[n]-s[j]+s[i-1]>=k*n-k*j+k*(i-1)，即(s[n]-k*n)-(s[j]-k*j)+(s[i-1]-i+1)>=0。令c[i]=s[i]-k*i。原式可化为c[n]-c[j]+c[i-1]>=0，即c[n]>=c[j]-c[i-1]。

所以每二分答案得到一个k，就可以得到一组c[i]。所以只要找到一组令c[j]-c[i-1]最大的i和j即可。如果最大的c[j]-c[i-1]>c[n]。然后注意一下第一个和第n个不能去（因为这个wa了好多次qaq）。这样就可以了。

最大的c[j]-c[i-1]用n^2枚举判断当然是不行的啊，所以可以处理c[i]的前缀最小值和后缀最大值，这样就可以o(n)check了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
int read()
{
    int f=1,p=0;
    char c=getchar();
    while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){p=p*10+c-'0';c=getchar();}
    return f*p;
}
double l,r,m;
int n,s[100100];
double hmax[100100],qmin[100100],c[100100];
bool check()
{
    for(int i=0;i<=n;i++)c[i]=s[i]-m*i;
    qmin[1]=c[1];for(int i=2;i<=n;i++)qmin[i]=min(qmin[i-1],c[i]);
    hmax[n-1]=c[n-1];for(int i=n-2;i>=1;i--)hmax[i]=max(hmax[i+1],c[i]);
    for(int i=2;i<n;i++)
        if(hmax[i]-qmin[i-1]>c[n])return 0;
    return 1;
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++)s[i]=s[i-1]+read();
    l=0,r=1e4+100;
    for(int i=1;i<=60;i++)
    {
        m=(l+r)/2;
        if(check())l=m;
        else r=m;
    }
    printf("%.3lf",l);
    return 0;
}