3203: [Sdoi2013]保护出题人
2013年6月03日 16:21
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);
}
