3144: [Hnoi2013]切糕

3203: [Sdoi2013]保护出题人

高橋直樹 posted @ 2013年6月03日 16:21 in BZOJ with tags SDOI bzoj , 1909 阅读

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

RunID User Problem Result Memory Time Language Code_Length Submit_Time
427418 Liu_Ts 3203 Accepted 5884 kb 264 ms C++ 1119 B 2013-06-03 15:47:57

 

题意

题目很复杂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);
}

 

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter