题目
题目描述
出题人铭铭认为给SDOI2012出题太可怕了，因为总要被骂，于是他又给SDOI2013出题了。
参加SDOI2012的小朋友们释放出大量的僵尸，企图攻击铭铭的家。而你作为SDOI2013的参赛者，你需要保护出题人铭铭。
僵尸从唯一一条笔直道路接近，你们需要在铭铭的房门前放置植物攻击僵尸，避免僵尸碰到房子。
第一关，一只血量为$a_1$点的墦尸从距离房子$x_1$米处速接近，你们放置了攻击力为$y_1$点/秒的植物进行防御；第二关，在上一关基础上，僵尸队列排头增加一只血量为$a_2$点的僵尸，与后一只僵尸距离$d$米，从距离房$x_2$米处匀速接近，你们重新放置攻击力为$y_2$点/秒的植物；……；第$n$关，僵尸队列共有$n$只僵尸，相邻两只僵尸距离$d$d米，排头僵尸血量为$a_n$点，排第二的 僵尸血量$a_{n-1}$，以此类推，排头僵尸从距离房子$x_n$米处匀速接近，其余僵尸跟随排头同时接近，你们重新放置攻击力为$y_n$点/秒的植物。
每只僵尸直线移动速度均为11米/秒，由于植物射击速度远大于僵尸移动速度，可忽略植物子弹在空中的时间。所有僵尸同时出现并接近，因此当一只僵尸死亡后，下一只僵尸立刻开始受到植物子弹的伤害。
游戏得分取决于你们放置的植物攻击力的总和$\sum \limits _{i=1} ^{n} y_i$，和越小分数越高，为了追求分数上界，你们每关都要放置攻击力尽量小的植物。
作为SDOI2013的参赛选手，你们能保护出题人么？
输入输出格式
输入格式：
第一行两个空格隔开的正整数n和d，分别表示关数和相邻僵尸间的距离。
接下来n行每行两个空格隔开的正整数，第i + 1行为Ai和 Xi，分别表示相比上一关在僵尸队列排头增加血量为Ai 点的僵尸，排头僵尸从距离房子Xi米处开始接近。
输出格式：
一个数，n关植物攻击力的最小总和 ，保留到整数。
输入输出样例
输入样例#1：
5 2
3 3
1 1
10 8
4 8
2 3
输出样例#1：
7
说明
第一关：距离房子3米处有一只血量3点的僵尸，植物最小攻击力为1.00000；
第二关：距离房子1米处有一只血量1点的僵尸、3米处有血量3点的僵尸，植物最小攻击力为1.33333；
第三关：距离房子8米处有一只血量10点的僵尸、10米处有血量1点的僵尸、12米处有血量3点的僵尸，植物最小攻击力为1.25000；
第四关：距离房子8米处有一只血量4点的僵尸、10米处有血量10点的僵尸、12米处有血量1点的僵尸、14米处有血量3点的僵尸，植物最小攻击力为1.40000；
第五关：距离房子3米处有一只血量2点的僵尸、5米处有血量4点的僵尸、7米处有 血量10点的僵尸、9米处有血量1点的僵尸、11米处有血量3点的僵尸，植物最小攻击力 为2.28571。
植物攻击力的最小总和为7.26905。
对于100%的数据， 1<=n<=10^5，1<=d<=10^12,1<=x<= 10^12,1<=a<=10^12
题解
首先对于第$i$关，最小攻击力为$max(\frac{sum_i-sum_{j-1}}{x_i+(i-j)\times d}),1\le j\le i$，其中$sum_i$表示到$i$关僵尸血量的前缀和
发现上面的式子就是求点$(x_i+i\times d,sum_i)$和$(j\times d,sum_{j-1})$的斜率的最大值
因为$sum$单调递增，$i\times d$也单调递增，所以点都会集中在第一象限，维护一个凸壳，然后在上面三分找斜率最大值就行了
起初$80$分死活找不出错后来发现$10^{12}\times 10^{12}$会爆long long……
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<cmath>
# include<algorithm>
# define LL double
using namespace std;
const int MAX=1e5+5;
struct Point{
LL x,y;
Point(LL X=0,LL Y=0) {x=X,y=Y;}
}_P[MAX],A,B;
int n,Top;
LL d;
double ans;
int st[MAX];
LL sum[MAX],X[MAX];
Point operator+ (Point x,Point y) {return Point(x.x+y.x,x.y+y.y);}
Point operator- (Point x,Point y) {return Point(x.x-y.x,x.y-y.y);}
LL Cross(Point x,Point y) {return x.x*y.y-x.y*y.x;}
LL read()
{
LL x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x;
}
int main()
{
n=read(),d=read();
for(int i=1;i<=n;++i)
sum[i]=sum[i-1]+read(),X[i]=read();
for(int i=1,l,r,k;i<=n;++i)
{
A=Point(X[i]+i*d,sum[i]),_P[i]=Point(i*d,sum[i-1]);
while(Top>1&&Cross(_P[st[Top]]-_P[st[Top-1]],_P[i]-_P[st[Top]])<=0) --Top;
st[++Top]=i,l=1,r=Top,k=1;
while(l+3<=r)
{
int midl=l+r>>1,midr=midl+r>>1;
if(Cross(_P[st[midl]]-A,_P[st[midr]]-A)<0) r=midr;
else l=midl;
}
double Ans=0;
B=_P[st[l]]-A,k=st[l];
for(int j=l+1;j<=r;++j)
if(Cross(_P[st[j]]-A,B)<0) B=_P[st[j]]-A,k=st[j];
ans+=double(A.y-_P[k].y)/double(A.x-_P[k].x);
}
return printf("%.0lf",ans),0;
}
