bzoj 3203 凸包+三分

题目大意

具体自己看吧link

读入n,D，表示n关

大概就是第i关有i只僵尸排成一队来打出题人

最前面那只是编号为\(i\)的僵尸，最后面的一只是编号为\(1\)的僵尸

最前面的僵尸离出题人\(X_i\)的距离,其它每只僵尸离前一只距离为固定值D

僵尸平均每秒1米，植物每秒攻击力\(y\)

植物连续攻击，可以当它激光，打死前一只瞬间就可以开始打后一只

对于每一关，我们要选择一个尽可能小的y，保证出题人不被打死

求y总和最小为多少

分析

我们考虑\(y\)要满足什么条件

首先要打死每只僵尸，极限是在它到出题人跟前时把它打死

这时我们总共攻击了\(dist*y\)的血量，打掉了那只僵尸的前缀和血量

\(y_i=max\{\frac {sum[i]-sum[j-1]} {x[i]+(i-j)*d}\}\)（i可以等于j）

转化为斜率形式

y2=sum[i], y1=sum[j-1]

x2=x[i]+id, x1=jd

将(x1,y1)用凸包维护一个下凸壳

用(x2,y2)在凸包上三分找到一个斜率最大的点

solution

#include <cstdio>

#include <cstdlib>

#include <cstdlib>

#include <cctype>

#include <cmath>

#include <algorithm>

using namespace std;

typedef long long LL;

typedef long double db;

const int M=100007;

inline LL rd(){

	LL x=0;bool f=1;char c=getchar();

	for(;!isdigit(c);c=getchar()) if(c=='-') f=0;

	for(;isdigit(c);c=getchar()) x=x*10+c-48;

	return f?x:-x;

}

int n;

db ans;

LL D,sum[M],bg[M];

struct pt{

	db x,y;

	pt(db xx=0,db yy=0){

		x=xx; y=yy;

	}

}stack[M];  int tot;

pt operator -(pt x,pt y){return pt(x.x-y.x,x.y-y.y);}

db operator ^(pt x,pt y){return x.x*y.x-x.y*y.y;}

db operator *(pt x,pt y){return x.x*y.y-y.x*x.y;}

db side(pt x,pt y,pt z){return (y-x)*(z-x);}

db slop(pt x,pt y){pt tp=y-x;return tp.y/tp.x;}

void ins(pt x){

	while(tot>1&&side(stack[tot-1],stack[tot],x)<0) tot--;

	stack[++tot]=x;

}

db get(pt x){

	int l=1,r=tot,m1,m2,le;

	db d1,d2;

	while(l+1<r){

		le=(r-l+1)/3;

		m1=l+le-1;

		m2=m1+le;

		d1=slop(stack[m1],x);

		d2=slop(stack[m2],x);

		if(d1<d2) l=m1+1;

		else r=m2-1;

	}

	return max(slop(stack[l],x),slop(stack[r],x));

}

int main(){

	int i;

	n=rd(),D=rd();

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

		sum[i]=sum[i-1]+rd();

		bg[i]=rd();

	}

	pt nw;

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

		nw=pt(i*D,sum[i-1]);

		ins(nw);

		nw=pt(bg[i]+i*D,sum[i]);

		ans+=get(nw);

	}

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

	return 0;

}

巴特西

bzoj 3203 凸包+三分

题目大意

分析

solution

最新文章

热门文章