Java教程

[loj2157]避雷针

本文主要是介绍[loj2157]避雷针,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

不难发现,问题即求$\forall 1\le i\le n,\max_{1\le j\le n}h_{j}+\sqrt{|i-j|}-h_{i}$

其中$h_{i}$是常数,并将$j$分为$<i$和$j>$两部分分别处理(以下以前者为例)

构造函数$g_{j}(x)=h_{j}+\sqrt{x-j}$,问题也即求$\forall 1\le i\le n,\max_{1\le j<i}g_{j}(i)$

考虑$g_{j_{1}}(x)$和$g_{j_{2}}(x)$(保证$j_{1}<j_{2}$​)的大小关系,注意到
$$
\Delta g(x)=g_{j_{2}}(x)-g_{j_{1}}(x)=(h_{j_{2}}+\sqrt{x-j_{2}})-(h_{j_{1}}+\sqrt{x-j_{1}})\\
\Delta g'(x)=(\sqrt{x-j_{2}})'-(\sqrt{x-j_{1}})'=\frac{1}{2}(\frac{1}{\sqrt{x-j_{2}}}-\frac{1}{\sqrt{x-j_{1}}})>0
$$
换言之,两者在交点左侧$g_{j_{1}}(x)>g_{j_{2}}(x),$交点右侧$g_{j_{1}}(x)<g_{j_{2}}(x)$(交点数量不超过1)

特别的,若$\Delta g(j_{2})>0$则认为交点在$-\infty$,若$\Delta g(\infty)<0$则认为交点在$\infty$(均指$x$坐标)

记$P(j_{1},j_{2})$表示$g_{j_{1}}(x)$和$g_{j_{2}}(x)$交点($x$坐标),从左到右枚举$i$并维护此时的函数"凸包",具体如下——

插入:加入函数$g_{i}(x)$时,设队次尾、队尾函数分别为$g_{j_{1}}(x)$和$g_{j_{2}}(x)$,不断弹出队尾直至$P(j_{1},j_{2})<P(j_{2},i)$

此时,若$P(j_{2},i)\ne \infty$,则在队尾加入$i$

查询:查询$i$处最大值时,设队首、对次首元素分别为$g_{j_{1}}(x)$和$g_{j_{2}}(x)$,不断弹出队首直至$i<P(j_{1},j_{2})$

此时,函数$g_{j_{1}}(x)$即为取到最大值的函数,即答案为$g_{j_{1}}(i)$

(两种情况均需注意队列大小不足的情况)

关于如何求$P(j_{1},j_{2})$,特判$\Delta g(j_{2})>0$和$\Delta g(\infty)<0$的情况(即交点不存在),进而即解方程
$$
h_{j_{1}}+\sqrt{x-j_{1}}=h_{j_{2}}+\sqrt{x-j_{2}}\\
\sqrt{x-j_{1}}-\sqrt{x-j_{2}}=h_{j_{2}}-h_{j_{1}}\\
\frac{(x-j_{1})-(x-j_{2})}{\sqrt{x-j_{1}}+\sqrt{x-j_{2}}}=h_{j_{2}}-h_{j_{1}}\\
\sqrt{x-j_{1}}+\sqrt{x-j_{2}}=\frac{j_{2}-j_{1}}{h_{j_{2}}-h_{j_{1}}}\\
$$
将其与第2个和第4个式子联立,不难解得
$$
2\sqrt{x-j_{1}}=(h_{j_{2}}-h_{j_{1}})+\frac{j_{2}-j_{1}}{h_{j_{2}}-h_{j_{1}}}\\
x=\left(\frac{(h_{j_{2}}-h_{j_{1}})+\frac{j_{2}-j_{1}}{h_{j_{2}}-h_{j_{1}}}}{2}\right)^{2}+j_{1}
$$
综上,时间复杂度为$o(n)$,可以通过

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define N 500005
 4 #define oo 0x3f3f3f3f
 5 int n,h[N],q[N],ans[N];
 6 double sqr(double x){
 7     return x*x;
 8 }
 9 int get_val(int i,int j){
10     return h[j]+(int)ceil(sqrt(i-j));
11 }
12 double get_point(int j1,int j2){
13     if (h[j1]+sqrt(j2-j1)<h[j2])return -oo;
14     if (h[j1]>=h[j2])return oo;
15     int dj=j2-j1,dh=h[j2]-h[j1];
16     return sqr((dh+1.0*dj/dh)/2)+j1;
17 }
18 void calc(){
19     int l=1,r=0;
20     for(int i=1;i<=n;i++){
21         while ((l<r)&&(get_point(q[l],q[l+1])<=i))l++;
22         if (l<=r)ans[i]=max(ans[i],get_val(i,q[l]));
23         while ((l<r)&&(get_point(q[r],i)<=get_point(q[r-1],q[r])))r--;
24         if ((l>r)||(get_point(q[r],i)!=oo))q[++r]=i;
25     }
26 }
27 int main(){
28     scanf("%d",&n);
29     for(int i=1;i<=n;i++)scanf("%d",&h[i]);
30     calc(),reverse(h+1,h+n+1),reverse(ans+1,ans+n+1);
31     calc(),reverse(h+1,h+n+1),reverse(ans+1,ans+n+1);
32     for(int i=1;i<=n;i++)ans[i]=max(ans[i]-h[i],0);
33     for(int i=1;i<=n;i++)printf("%d\n",ans[i]);
34     return 0;
35 }
View Code

 

这篇关于[loj2157]避雷针的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!