题解：P11677 [USACO25JAN] Shock Wave P

· · 题解

下文默认 1-index。

注意到对于 1<x<n 的位置，至多进行一次操作。证明就是考虑若选了两个非 1,n 位置 x\le y 进行操作，会发现不如操作 x-1,y+1 优。令最终 1 操作了 a 次，n 操作了 b 次。我们先二分出只用 1,n 操作的答案，随后 check 下答案能否通过非 1,n 操作取到 ans-1 即可。

二分出仅用 1,n 操作的答案是容易的。令 a+b=mid，分别讨论 2i\le n,2i=n+1,2i>n+1 可以得到 a,b 的下界，判断两个下界加起来是否小于等于 mid 即可。注意这里要特判分母为 0 的情况。下文令这个二分出来的答案为 ans。

现在我们加上中间的操作 m，重新写一下上面 check 的式子，会多出来一项 -|m-i|。暴力做是平方老哥级别的，无法通过。注意到下界的分母是 n-2i+1/2i-n-1 这启示我们考虑本质不同的下界取值，注意到其只有 O(n\log n) 种，因此我们用两个优先队列（里面放 m,i 与当前下界）维护当前最严格的下界限制，每次暴力更新下界即可，复杂度 O(n\log n\log V)。注意这里由于分母的正负性，需要从左至右以及从右至左跑两遍。

说下实现细节。