zd 讲的啥玩意啊。
题意
你初始的能量为 \(0\),每秒会回复一点能量,同时你每秒可以花 \(x\in [0,2]\) 点能量行走 \(x\) 的距离。
同时地上会有 \(n\) 个传送带,传送带的基础速度为 \(s_i\),求从 \(0\) 走到 \(L\) 的最短时间。
sol
神题吧。
首先你先把地上没有传送带的地方也看成一个速度为 \(0\) 的传送带,然后你给所有的传送带速度加 \(1\),那么你的速度就是 \([-1,1]\) 的范围了,原因下面会讲。
因为我们要求最快走到 \(L\),所以我们直接拉满这个速度,把他顶到当前传送带的极速 \(v+1\)。
这个时候我们就会倒欠能量,所以说我们需要前面把能量补过来,类似于反悔贪心。
假设我们当前想要的能量为 \(E\),对于前面一个人就要满足 \(\frac{L}{v'-x} x=E\),其中 \(L\) 是这个传送带的长度,\(v'\) 是这个传送带的速度,\(x\) 是减少的速度。
那么我们答案的增量就是 \(ans+=\frac{L}{v'-x} - \frac{L}{v'}\) 通分一下会发现这个形式非常滴优美:
\(ans+=\frac{E}{v'}\) 这下只需要挑当前最大速度的选就行了,随便挑个数据结构维护一下即可。