看灵神题解看半天，看的脑壳疼。不知道是不是完全理解了。
总体来说是使用BFS来从起点状态，枚举一次操作后可能出现的下一个状态。再由下一层的状态继续枚举。直到所有的节点都被访问过。如果该办法不进行优化，单单是BFS的话，意味着每次判断区间节点是否被访问过，都要完整遍历可取的状态区间一次，时间复杂度就到了\(O(NK)\)，其中\(K\)为区间长度。
如果使用有序集合的话，可以将访问过的状态弹出，这样每次寻找到都直接是未经访问过的状态，大大节省了时间。然而这还不是最优的，因为你仍然需要去判断这些未访问的区间中的状态，哪些是下一次可能访问到的，哪些不是。
因为本题的特殊性质，可以使用两个有序集合进一步把区间中未访问的部分二分，将当前的状态与下一步访问的集合一一对应。直接从对应的集合中获取区间中的状态即可，无需额外判断。这保证了每个状态/节点，只会被访问常数次，从而将时间复杂度压缩到了\(O(nlogn)\)，其中\(logn\)是有序集合的维护开销。
BFS+有序集合
本题目中支持双有序集合的点在于从当前状态出发，其下一个访问的状态的性质是可以提前预知的。
假设二进制串总长度为 \(n\) ，其中 \(0\) 的数目是 \(z\) ，\(1\) 的数目是即是 \(n-z\) 。选择翻转时，选择翻转 \(0\) 的数目是 \(x\) ，那么被翻转的 \(1\) 的数目即是 \(k-x\) 。那么进行一次翻转操作后\(0\)的数目更新为：\(z=z+(k-x)-x=z+k-2x\) 。这个式子决定了为什么能使用双有序集合。如果将更新后的 \(z\) 对 \(2\) 进行取模。很容易发现其值由 \(z+k\) 决定，与 \(x\) 无关。也就是不论本次选择翻转多少，下一次 \(z\) 的状态必为奇或偶而不可能混带奇和偶。因此可以分别使用两个有序集合，一个维护奇，一个维护偶。
奇偶确定了，选择的集合也就确定了。还需要知道的是，下一个状态是集合中的哪个区间。对于\(z=z+k-2x\)更新公式而言，唯一的变量就是\(x\)，\(x\)的范围决定了选取的范围。对于\(x\)，其首先不能超过上限 \(z\) ，其次不允许超过允许翻转的数目 \(k\) ，下限不能低于\(0\)。除此之外\(1\)的数目也不能超过整体 \(1\) 的数目，有约束 \(k-x\)<=\(n-z\) 。综合以上，\(x\in [max(k,z),min(0，k+z-n)]\) 。剩下的问题就很简单了。使用BFS逐层枚举即可。
class Solution:def minOperations(self, s: str, k: int) -> int:n = len(s)# 一个存储奇状态，一个存偶状态not_vis = [SortedList(range(0,n+1,2)),SortedList(range(1,n+1,2))]# 避免后续需要判断idx不存在以及循环越界问题not_vis[0].add(n+1)not_vis[1].add(n+1)start=s.count('0') # 起始状态# 从未访问中去除startnot_vis[start%2].discard(start)# 以下为BFS带深度的写法，因为本题深度即是答案，这样写方便q=[start]ans=0while q:tmp=qq=[]for z in tmp:if z==0:return ansmn=z+k-2*min(k,z)mx=z+k-2*max(0,k-n+z)# 只可能翻转到与mn奇偶相同的位置sl=not_vis[mn%2]# 二分查找能够达到的状态idx=sl.bisect_left(mn)while sl[idx] <= mx:j = sl.pop(idx)q.append(j)# 维护深度ans+=1 return -1