OI - Landmarks(Codeforces) | Lucky_Glass's Blog
0%

OI - Landmarks(Codeforces)

上课的时候以为听懂了系列(然后发现其实啥都没懂)


# 题面

一个质量均匀分布的横梁由 $n+2$ 个高度相同的柱子支撑。柱子的位置可以抽象在数轴上,从左到右编号为 $0\sim n+1$,第 $i$ 个柱子在 $x_i$ 处,它的承重能力是 $d_i$;特别的,柱子 $0$ 和 $n+1$ 的承重能力为 $+\infty$。

对于相邻的两根柱子 $u$ 和 $v$,每根柱子承受它们之间的横梁的重量的一半。若一个柱子承受的重量超过其能力,它就会坍塌(消失)。

现在你要指定一个位置加一根柱子(承重能力自己指定),使得最后除了柱子 $0$ 和 $n+1$,还有柱子留下;特别的,如果加柱子的位置原本有柱子,原来的柱子就会被新柱子替换掉;并且你加的柱子的位置、承重能力都是非负实数。求加的柱子的最小承重能力。

数据规模:$1\le n\le10^5$,$0\le x_i,d_i\le10^9$。


# 解析

先判断是否一开始就可以有中间的柱子留下(判断方法后面写),如果是,则答案为 $0$。下面的解析默认忽略这种情况。

由于一段横梁的重量由相邻两个柱子分担,容易发现加入一根横梁的目的是阻止最终与它相邻的两个柱子坍塌,并且显然加入的柱子不会坍塌。

于是不妨决策加入柱子后,最终与这个柱子相邻的柱子是哪两个,记为 $L,R$。这样就可以分成前后缀考虑,即分别考虑加入的柱子左边和右边各自留下了哪些柱子。明显的,$L,R$ 是否合法以及加入的柱子的承重能力仅取决于 $L,R$。

对于柱子 $i$ 计算 “假设 $i$ 不会倒,则最终的方案中,$i$ 的左边是哪个柱子”,记为 flef[i];同理,右边的柱子记为 frig[i]。考虑如何计算 flef[i]。可以从左到右计算每根柱子,用栈维护当前有哪些柱子(栈顶就是现在剩下的柱子中最右边的)。计算 flef[i] 时,判断栈顶的柱子会不会坍塌,直到找到不会坍塌的柱子即为 flef[i],然后把 $i$ 入栈。

如果计算出来 flef[n+1] 不是 $0$,则说明不用加柱子就已经合法。

同理求得 frig[i] 后,可以求得,如果 $i$ 不坍塌

  • 则 $i$ 右边至少在哪个位置要有柱子:$\frac{x-flef_i}2\le d_i\to x\le 2d_i+flef_i$;
  • 则 $i$ 左边至少在哪个位置要有柱子:$\frac{frig_i-x}2\le d_i\to x\ge frig_i-2d_i$。

如果 $L,R$ 满足

则可以在 $L,R$ 之间放一根柱子使该方案合法。前两个不等式保证了 $L$ 左边的重量不会使 $L$ 坍塌、$R$ 右边的重量不会使 $R$ 坍塌,第三个不等式保证了存在一种在 $L,R$ 之间放柱子的方案使得 $L,R$ 都不坍塌。另外,可以看出无论在 $L,R$ 之间哪个位置加柱子,加的柱子的承重能力都是 $\frac{x_R-x_L}2$,于是只需要找合法的最小的 $x_R-x_L$。

双端点问题可以考虑枚举一个端点,比如 $R$;$R$ 确定后,就相当于是找最大的满足条件的 $L$。容易发现,如果 $L_2>L_1$ 并且 $flef_{L_2}+2d_{L_2}\ge flef_{L_1}+2d_{L_1}$,则 $L_1$ 一定就没有用了。于是可以从左到右扫描,用单调栈维护 $flef_i+2d_i$ 单减的序列,对于 $R$ 在单调栈上二分 $flef_i+2d_i\ge frig_R-2d_R$ 的最大 $i$。


# 源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

template<class T>inline T Rint(T &r){
int b=1,c=getchar();r=0;
while(c<'0' || '9'<c) b=c=='-'? -1:b,c=getchar();
while('0'<=c && c<='9') r=(r<<1)+(r<<3)+(c^'0'),c=getchar();
return r*=b;
}
const int N=1e5+10;

int n,m;
int aryx[N],stk[N],flef[N],frig[N];
long long aryd[N];

int main(){
// freopen("input.in","r",stdin);
Rint(n);
for(int i=0;i<=n+1;i++) Rint(aryx[i]);
for(int i=1;i<=n;i++) Rint(aryd[i]);
aryd[0]=aryd[n+1]=1e9+7;
//flef[i] 假设i不会坍塌,i向左最近能reach到哪个位置
//stack 中储存的是“假设i不会坍塌,哪些柱子会留下来”
stk[m=1]=0;
for(int i=1;i<=n+1;i++){
while(m>1 && 2*aryd[stk[m]]<aryx[i]-aryx[stk[m-1]])
m--;
flef[i]=aryx[stk[m]];
stk[++m]=i;
}
//frig[i] 向右同理
stk[m=1]=n+1;
for(int i=n;~i;i--){
while(m>1 && 2*aryd[stk[m]]<aryx[stk[m-1]]-aryx[i])
m--;
frig[i]=aryx[stk[m]];
stk[++m]=i;
}
//如果n+1能reach到中间的柱子,则中间的柱子就可以留下
if(flef[n+1]){printf("%f\n",0.0);return 0;}
stk[m=1]=0;
int ans=aryx[n+1]-aryx[0];
for(int i=1;i<=n+1;i++){
int nL=1,nR=m;
//二分左边最近的合法区间与i有交的点
while(nL+1<nR){
int nM=(nL+nR)>>1;
if(flef[stk[nM]]+2*aryd[stk[nM]]>=frig[i]-2*aryd[i]) nL=nM;
else nR=nM;
}
int it=0; //0必然合法
if(flef[stk[nR]]+2*aryd[stk[nR]]>=frig[i]-2*aryd[i]) it=stk[nR];
else if(flef[stk[nL]]+2*aryd[stk[nL]]>=frig[i]-2*aryd[i]) it=stk[nL];
//i本身左合法(还可以向左延伸)
if(frig[i]-2*aryd[i]<aryx[i])
ans=min(ans,aryx[i]-aryx[it]);
//i本身右合法(还可以向右延伸)
if(flef[i]+2*aryd[i]>aryx[i]){
while(m && 2*aryd[i]+flef[i]>=2*aryd[stk[m]]+flef[stk[m]]) m--;
stk[++m]=i;
}
}
printf("%f\n",ans/2.0);
return 0;
}

THE END

Thanks for reading!

> Linked 何日重到苏澜桥-Bilibili