http://www.lydsy.com/JudgeOnline/problem.php?id=3203

题意

题目很复杂0.0

对于每一关，会加一个血量为a[i]的僵尸在队首，每个僵尸之间间隔d，

队首的坐标为x[i]，僵尸移动速度1单位长度/s

每次求一个植物的最小攻击力y[i]点血/s，使得出题人不被吃掉的情况下，打死所有僵尸。

注意：如果某次植物攻击，大于当前僵尸的血量，超出的攻击力会打到下一个僵尸。

题解

设s[i]=sigm(a[i])

则y[i]=max{(s[i]-s[j-1])/(x[i]+（i-j）*d)}  (i≥j);

于是对于每个僵尸j我们设点（j*d，s[j-1]），

那么答案就相当于每次给定一个点（x[i]+i*d，s[i]），

在当前僵尸中求一个点使得这两个点的斜率最大。

这样维护下凸壳，再二分就可以了。

#include<cstring>
#include<algorithm>
#include<cmath>
#include<climits>
#include<cstdio>
using namespace std;
typedef long long ll;
typedef long double ld;
const int N=100010;
const double eps=1e-8;
struct point
{
    ld x,y;
}p[N],c;
int n,q[N],top;
ld s[N],x[N],d,ans;
 
ld cross(point c,point a,point b)
{
    return (a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y);
}
 
int find()
{
    int tmp=1,l=2,r=top,mid;
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(cross(c,p[q[mid]],p[q[mid-1]])<-eps)
            tmp=max(tmp,mid),l=mid+1;
        else r=mid-1;
    }
    return tmp;
}
  
int main()
{
    double o1,o2;
    scanf("%d%lf",&n,&o1);d=o1;
    for(int i=1;i<=n;i++)
    {
        scanf("%lf%lf",&o1,&o2);s[i]=o1,x[i]=o2,s[i]+=s[i-1];
        p[i].x=i*d;p[i].y=s[i-1];
    }
    int j;
    for(int i=1;i<=n;i++)
    {
        while(top>1 && cross(p[q[top-1]],p[q[top]],p[i])<-eps) top--;
        q[++top]=i;c.x=x[i]+i*d;c.y=s[i];j=q[find()];
        ans+=(c.y-p[j].y)/(c.x-p[j].x);//printf("%.5lf\n",(double)ans);
    }
    printf("%.0lf\n",(double)ans);
}