2612.最少翻转操作数

链接：2612.最少翻转操作数
难度：Hard
标签：广度优先搜索、数组、有序集合
简介：请你返回一个数组 ans ，对于 [0, n - 1] 之间的任意下标 i ，ans[i] 是将 1 放到位置 i 处的 最少 翻转操作次数，如果无法放到位置 i 处，此数为 -1 。

题解 1 - cpp

• 编辑时间：2023-04-02
• 执行用时：716ms
• 内存消耗：163.36MB
• 编程语言：cpp
• 解法介绍：bfs+利用排序树快速删除和查找。

class Solution {
   public:
    vector<int> minReverseOperations(int n, int p, vector<int> &banned, int k) {
        vector<int> res(n, -1);
        res[p] = 0;
        if (k == 0 || k == 1) return res;
        unordered_set<int> used(banned.begin(), banned.end());
        set<int> ss[2];
        ss[0].insert(n);
        ss[1].insert(n);
        for (int i = 0; i < n; i++) {
            if (i != p && !used.count(i)) ss[i % 2].insert(i);
        }
        queue<int> q;
        int size = 1, cnt = 1;
        q.push(p);
        while (q.size()) {
            int p = q.front(), 
                nmin = max(p - k + 1, k - p - 1), 
                nmax = min(p + k - 1, 2 * n - k - p - 1);
            q.pop();
            auto it = ss[nmin % 2].lower_bound(nmin);
            while (*it <= nmax) {
                cout << "it= " << *it << endl;
                res[*it] = cnt;
                q.push(*it);
                ss[nmin % 2].erase(*it++);
            }
            if (--size == 0) {
                cnt++;
                size = q.size();
            }
        }
        return res;
    }
};