BZOJ 3203 sdoi 2013 保护出题人

由于样例解释很清晰，所以很容易得到以下结论：

1、每一关都是独立的，且僵尸的相对位置不会变

2、每一关的攻击力=Max（sum(i)/dis(i))

其实sum(i)是僵尸攻击力的前缀和，dis(i)是距离

然后因为输入是每次在队头添加，所以我们可以把前缀和转换成后缀和

攻击力=Max( (sum_i-sum_j)/（x_i+i*d-j*d) )

这显然是一个斜率的式子，又因为僵尸的相对位置不变

所以我们可以维护一个下凸壳，之后每次在凸壳上三分最优解即可

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<cstdlib>

#define eps 1e-8

using namespace std;

const int maxn=100010;

int n,top=0,cur;

double d,ans;

double A[maxn],X[maxn];

double sum[maxn];

struct Point{

    double x,y;

    Point(double x=0,double y=0):x(x),y(y){}

};

Point st[maxn];

typedef Point Vector;

Vector operator -(const Point &A,const Point &B){return Vector(A.x-B.x,A.y-B.y);}

double Cross(const Point &A,const Point &B){return A.x*B.y-A.y*B.x;}

double F(int x){

    return (sum[cur]-st[x].y)/(X[cur]+cur*d-st[x].x);

}

int main(){

    scanf("%d%lf",&n,&d);

    for(int i=1;i<=n;++i)scanf("%lf%lf",&A[i],&X[i]),sum[i]=sum[i-1]+A[i];

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

        Point now=Point(d*i,sum[i-1]);

        while(top>=2&&Cross(now-st[top],st[top]-st[top-1])>eps)top--;

        st[++top]=now;cur=i;

        int L=1,R=top;

        while(R-L>=3){

            int m1=(L+L+R)/3,m2=(L+R+R)/3;

            if(F(m1)>F(m2))R=m2;

            else L=m1;

        }

        double sum=-1e18;

        for(int j=L;j<=R;++j)sum=max(sum,F(j));

        ans+=sum;

        //printf("%.8lf\n",sum);

    }printf("%.0lf\n",ans);

    return 0;

}

巴特西

BZOJ 3203 sdoi 2013 保护出题人

最新文章

热门文章