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
",ans);
	return 0;
}