LeetCode 2612 最少翻转次数：BFS 与有序集合的解法

并且 j 的奇偶性与 j_min（或 j_max）相同，遍历时只需隔 2 跳着取。

算法实现

如果用普通的 BFS，每层都去检查整个范围内奇偶相同的下标，复杂度会炸。我们需要快速定位那些仍未访问过的、且落在 [j_min, j_max] 内、奇偶性正确的下标。

一个很自然的优化是预处理出所有未访问的奇数和偶数下标，分别放到两个有序集合（如 C++ 的 std::set）里。BFS 时，对当前 i 计算出 j_min 和 j_max，然后在对应奇偶性的集合里，从 lower_bound(j_min) 开始迭代，只要没超过 j_max 就更新答案、入队，并把该下标从集合中删除。set 的 erase 返回下一个迭代器，遍历和删除非常顺手。

需要注意，初始时 p 已经访问过，不应该再出现在集合里；banned 里的下标直接忽略，永远不能进入集合。

代码整理如下：

class Solution {
public:
    vector<int> minReverseOperations(int n, int p, vector<int>& banned, int k) {
        unordered_set<int> ban(banned.begin(), banned.end());
        set<int> index[2]; // 0: 偶数未访问, 1: 奇数未访问
        for (int i = 0; i < n; i++) {
            if (i != p && !ban.count(i)) {
                index[i % 2].insert(i);
            }
        }
        queue<int> q;
        q.push(p);
        vector<int> ans(n, -1);
        ans[p] = 0;

        while (q.size()) {
            int i = q.front(); q.pop();
            int mn = max(i - k + 1, k - i - 1);
            int mx = min(i + k - 1, 2 * n - k - i - 1);
            auto& st = index[mn % 2];
            for (auto it = st.lower_bound(mn); it != st.end() && *it <= mx; it = st.erase(it)) {
                ans[*it] = ans[i] + 1;
                q.push(*it);
            }
        }
        return ans;
    }
};

BFS 保证了第一次访问某个下标时得到的步数就是最少翻转次数，因为边权全是 1。利用有序集合避免重复扫描未访问元素，整体复杂度大约 O(n log n)，可以顺利通过题目限制。