BZOJ 3203 [SDOI2013]保护出题人 (凸包+三分)

洛谷传送门

题目大意：太长略

每新加入一个僵尸，容易得到方程$ans[i]=max{\frac{sum_{i}-sum_{j-1}}{s_{i}+d(i-j)}}$

即从头开始每一段僵尸都需要在规定距离内被消灭

展开式子，可得$ans[i]=max{\frac{sum_{i}-sum_{j-1}}{s_{i}+di-dj}}$

是不是很像斜率的式子= = ----$(y2-y1)/(x2-x2)$

维护一个下凸包，这次不是用直线去切凸包，而是把凸包上每个点都向一个定点去连直线，求最大的斜率

会发现，凸包上连出来的直线的斜率是一个凸函数，再利用三分法进行查找

三分法类似于一个爬坡的过程，每次都缩小两侧山坡范围，最终找到山顶

至于为什么维护下凸包呢，画个图就明白了，如果之前某个点$a$，与点$b(b_{x}<a_{x})$的斜率，大于新加入的点$i$与$b$的斜率，那么如果右侧出现一个点，向他们连直线，显然$i$的斜率大于$a$，可以用三角形的性质去证

因为$x$递增，用单调栈维护下凸包即可

时间$O(nlogn)$

貌似比较斜率必须用$double$，不然爆$long\;long$

 #include <cmath>

 #include <queue>

 #include <vector>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #define N1 101000

 #define M1 205

 #define ll long long

 #define dd double

 #define uint unsigned int

 using namespace std;

 ll gll()

 {

     ll ret=;int fh=;char c=getchar();

     while(c<''||c>''){if(c=='-')fh=-;c=getchar();}

     while(c>=''&&c<=''){ret=ret*+c-'';c=getchar();}

     return ret*fh;

 }

 int n;

 ll D;

 ll a[N1],s[N1],sa[N1];

 ll x[N1],y[N1];

 int stk[N1],tp;

 inline dd gslope(int i,int j){

     return 1.0*(y[i]-y[j])/(x[i]-x[j]);

 }

 int main()

 {

     //freopen("t2.in","r",stdin);

     scanf("%d%lld",&n,&D);

     for(int i=;i<=n;i++)

         a[i]=gll(),s[i]=gll(),sa[i]=sa[i-]+a[i];

     dd ans=;

     for(int i=;i<=n;i++)

     {

         x[i]=1.0*i*D,y[i]=sa[i-];

         while(tp>&&gslope(stk[tp],stk[tp-])>=gslope(i,stk[tp-]))

             tp--;

         stk[++tp]=i;

         int l=,r=tp,mid1,mid2;

         x[]=1.0*s[i]+1.0*D*i,y[]=sa[i];

         while(r-l>=)

         {

             mid1=(l+l+r)/,mid2=(l+r+r)/;

             if(gslope(,stk[mid1])>gslope(,stk[mid2]))

                 r=mid2;

             else

                 l=mid1;

         }

         dd ma=;

         for(int j=l;j<=r;j++)

             ma=max(ma,gslope(,stk[j]));

         ans+=ma;

     }

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

     return ;

 }

巴特西

BZOJ 3203 [SDOI2013]保护出题人 (凸包+三分)

最新文章

热门文章