【吐槽：我不想保护出题人。。。】

首先把读入的a数组变成前缀和。然后就可以发现y数组其实就是这个东西这就是确保杀死j~i(j≤i)这一段僵尸的最小速度。伤害的和是a[i]-a[j-1]，第j个~第i个之间的距离是di-dj，还要加上x[i]才是与家的距离。很绕吗？自己脑补吧。。

观察这个式子比较像求直线的斜率。那么我们把它转化为两点之间的斜率好了。把跟i有关的看成一个点，跟j有关的看成一个点。

那么就是(x[i]+d*i,a[i])和(d*j,a[j-1])两个点。然后只要求斜率了！！！

那么用单调栈维护一个凸壳就好了！！！计算斜率的时候二分。二分的时候先判是不是在凸壳的外部，然后取栈里面最上面那个就好了。

很好。nlogn了。

这是样例，有线连着的点是转化过的(d*j,a[j-1])。其中虚线是最后形成的凸壳。

查询第i次的时候就是先转化为(x[i]+d*i,a[i])这个点，然后二分凸壳上的点求最大的斜率就好。

比如查询第一次。凸壳（黄线）中只有(2,0)这个点。要查询的是(5,3)。很明显斜率只能是1。

查询第二次。查询的点是(5,4)。凸壳中有两个点(2,0)，(4,3)。选前者的算出的斜率1.3333比后者的1要优。

然后以此类推就可以解决全部询问。

这道题在八中上rank1了我会告诉你们？介于是rank1我就不发rank1的代码了、、这个是目前rank10的、、

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef double D; D a[100005],x[100005],d,An=0;
struct P{D x,y;P(){};P(D _x,D _y):x(_x),y(_y){};}p[100005];
D cross(P a,P b,P c){ return (a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y);}
int st[100005],top=0,n;
int main(){
    scanf("%d%lf",&n,&d);
    for(int i=1;i<=n;i++){
        scanf("%lf%lf",&a[i],&x[i]);
        a[i]+=(p[i].y=a[i-1]);  p[i].x=i*d;
    }for(int i=1;i<=n;i++){
        while(top&&cross(p[st[top]],p[i],p[st[top-1]])<0)top--;
        st[++top]=i;     P s(x[i]+i*d,a[i]);
        int j=1,l=1,r=top,mid;  while(l<=r){
            mid=l+r>>1;
            if(cross(p[st[mid]],p[st[mid-1]],s)<0)j=max(j,mid),l=mid+1;else r=mid-1;
        }An+=(s.y-p[st[j]].y)/(s.x-p[st[j]].x);
    }printf("%.0lf\n",An);  return 0;
}

• 相关文章