给你一个字符串 S,由 Y
和 .
构成。
现在你可以最多进行 k 次操作,每次可以交换两个相邻的字符。
请你求出最多 k 次操作后,最长连续字符 Y
的长度。
- 2≤∣S∣≤2×105
- 0≤K≤1012
设 A 为 S 中 Y
的位置从小到大构成的序列,令 Bi=Ai−i,那么问题就转化为:
每次操作可以选择一个 i,让 Bi→Bi+1 或者 Bi→Bi−1,最多进行 k 次操作,求操作之后最长的 Bi 相同的连续段。
考虑尺取,假设当前区间为 [l,r],那么最少需要的操作次数显然就相当于这个函数的最小值:
f(x)=i=l∑r∣Bi−x∣
不难发现这是个小学奥数题,显然 x=Bi+⌊2r−l+1⌋ 即最中间时 f(x) 是最小的,那么只要判断 f(Bi+⌊2r−l+1⌋) 小于等于 k 即可。