P2571[SCOI2010]传送带 题解

nekko · 2021-07-31 02:29:52 · 个人记录

\max(P,Q) \le R

也就是说在平面上跑最快，那么不需要经过传送带优化速度

\min(P,Q) \ge R

不妨设 P \ge Q \ge R（因为 A \to D 和 D \to A 本质相同，传送带无方向）

那么 \frac{AE}{P}+\frac{EF}{R}+\frac{FD}{Q}=\frac{1}{R}\left( AE \cdot \frac{R}{P} + EF +FD \cdot \frac{R}{Q} \right)

记 \tau= AE \cdot \frac{R}{P} + EF +FD \cdot \frac{R}{Q} ，目标最小化 \tau

其中 \max(\frac{R}{P},\frac{R}{Q}) \le 1

不妨设 \sin \alpha =\frac{R}{P},\sin \beta=\frac{R}{Q},0 < \alpha \le \beta \le \frac{\pi}{2}

作辅助线 AM,AN,\angle BAM=\alpha, \angle CDN= \beta

作 EH \perp AM,FI \perp DN，则 EH=AE \sin \alpha, FI=FD \sin \beta

则 \tau=EH+EF+FI

当 E 固定时，(EF+FI)_{\min} 在 EI \perp DN 时取得最小值（当然也可能在 I 和 D 重合的时候取到，在此不做考虑）

修正后的图像如下：

此时 \tau=EH+EI

当 E 在 \vec{BA} 延长线上时，随 E 远离 A，有 EH,ED 逐渐增大

当 E 在 \vec{AB} 延长线上时，随 E 远离 AB \cap ND，有 EH,ED 逐渐增大

考虑这样一个图（延长了 AB 使得 AB \cap ND）

现在的目标是探索 RQ+QS 的值的变化，显然 Q 在线段 KT 外的变化都是单调（增）的

不难发现，(rq+qs)-(RQ+QS)=qQ(\sin \angle 1-\sin \angle 2) 而且 \angle 1,\angle 2 为定值

又因为 qQ>0，所以 (rq+qs)-(RQ+QS) 符号确定

因此随着 Q 在线段 KT 上单调移动，RQ+QS 是单调的（最小值要么在 K 取到，要么在 T 取到）

因此 Q 在直线 KT 上移动时，RQ+QS 是单峰的

因此原图 E 的坐标可以三分（第一个问题证明完了）

实际上当 E 固定之后，EI 的值可以直接计算出来，当然也可以三分

当 F' 在 FC 上时，随 F' 靠近 C，有 EF',F'I' 单调（增）

当 F' 在 FD 上时，(EF''+F''I'')-(EF'+F'I')=EF''-(EF'+F'Y) > EF''-EX>0

故随 F' 靠近 D，有 EF'+F'I' 单调（增）

因此 EF+FI 是单峰的，可以三分了