ABC229G Longest Y 做题记录

给你一个字符串 $S$，由 Y 和 . 构成。

现在你可以最多进行 $k$ 次操作，每次可以交换两个相邻的字符。

请你求出最多 $k$ 次操作后，最长连续字符 Y 的长度。

• $2 \leq |S| \leq 2 \times 10^5$
• $0 \leq K \leq 10^{12}$

设 $A$ 为 $S$ 中 Y 的位置从小到大构成的序列，令 $B_i=A_i-i$，那么问题就转化为：

每次操作可以选择一个 $i$，让 $B_i\to B_i+1$ 或者 $B_i\to B_i-1$，最多进行 $k$ 次操作，求操作之后最长的 $B_i$ 相同的连续段。

考虑尺取，假设当前区间为 $[l,r]$，那么最少需要的操作次数显然就相当于这个函数的最小值：

$f(x)=\sum\limits_{i=l}^r|B_i-x|$

不难发现这是个小学奥数题，显然 $x=B_{i+\lfloor\frac{r-l+1}{2}\rfloor}$ 即最中间时 $f(x)$ 是最小的，那么只要判断 $f(B_{i+\lfloor\frac{r-l+1}{2}\rfloor})$ 小于等于 $k$ 即可。