LC 2612. 最少翻转操作数

https://leetcode.cn/problems/minimum-reverse-operations/

这题最开始想到了使用BFS来搞，但是中间有两个问题：

  1. 枚举从i可以置换到的位置，说实话这个有点绕
  2. 如果k很大的话，那么每次i可以枚举的位置会很多，怎么进行剪枝。

关于2，通常我们BFS的时候边不会太多，但是这个题目边会特别多。所以我们不能枚举点再去check, 而必须去筛选那些没有被选中的点。

关于1，我一开始有过许多奇奇怪怪的枚举办法，但是都有各种各样的问题：

  1. 首先可以置换位置必须满足奇偶性，(x + y + 1)% 2 == k % 2
  2. 我们可以先求最低位，然后不断向上遍历，直到条件不满足位置。
  3. 不满足的条件就是， 如果(x, y)交换，那么可以延展的范围必须在数组内。
  4. 我们在筛选那些没有选中点的时候，必须也考虑到奇偶性，不然搜索空间就会很大了。
class Solution:
    def minReverseOperations(self, n: int, p: int, banned: List[int], k: int) -> List[int]:
        from sortedcontainers import SortedList
        opts = [SortedList(), SortedList()]
        for i in range(n):
            opts[i % 2].add(i)
        for x in banned:
            opts[x % 2].remove(x)

        from collections import deque
        dq = deque()
        ans = [-1] * n
        dq.append(p)
        ans[p] = 0
        opts[p % 2].remove(p)

        def search(x):
            y = max(x + 1 - k, k - x - 1, 0)
            if (x + y + 1) % 2 != k % 2:
                y += 1
            opt = opts[y % 2]
            idx = opt.bisect_left(y)
            while idx < len(opt):
                y = opt[idx]
                a, b = x, y
                if a > b:
                    a, b = b, a
                m = (k - (b - a + 1)) // 2
                if m >= 0 and (a - m) >= 0 and (b + m) < n:
                    yield a if a != x else b
                else:
                    break
                idx += 1

        while dq:
            x = dq.popleft()
            values = []
            for y in search(x):
                values.append(y)

            print(x, values)
            for v in values:
                opts[v % 2].remove(v)

            for y in values:
                ans[y] = ans[x] + 1
                dq.append(y)

        return ans