最少翻转操作数

题目

6365. 最少翻转操作数

---

给你一个整数 n 和一个在范围 [0, n - 1] 以内的整数 p ，它们表示一个长度为 n 且下标从 0 开始的数组 arr ，数组中除了下标为 p 处是 1 以外，其他所有数都是 0 。

同时给你一个整数数组 banned ，它包含数组中的一些位置。banned 中第 i 个位置表示 arr[banned[i]] = 0 ，题目保证 banned[i] != p 。

你可以对 arr 进行 若干次 操作。一次操作中，你选择大小为 k 的一个 子数组 ，并将它 翻转 。在任何一次翻转操作后，你都需要确保 arr 中唯一的 1 不会到达任何 banned 中的位置。换句话说，arr[banned[i]] 始终 保持 0 。

请你返回一个数组 ans ，对于 [0, n - 1] 之间的任意下标 i ，ans[i] 是将 1 放到位置 i 处的 最少 翻转操作次数，如果无法放到位置 i 处，此数为 -1 。

• 子数组 指的是一个数组里一段连续 非空 的元素序列。
• 对于所有的 i ，ans[i] 相互之间独立计算。
• 将一个数组中的元素 翻转 指的是将数组中的值变成 相反顺序 。

示例 1：

输入：n = 4, p = 0, banned = [1,2], k = 4
输出：[0,-1,-1,1]
解释：k = 4，所以只有一种可行的翻转操作，就是将整个数组翻转。一开始 1 在位置 0 处，所以将它翻转到位置 0 处需要的操作数为 0 。
我们不能将 1 翻转到 banned 中的位置，所以位置 1 和 2 处的答案都是 -1 。
通过一次翻转操作，可以将 1 放到位置 3 处，所以位置 3 的答案是 1 。

示例 2：

输入：n = 5, p = 0, banned = [2,4], k = 3
输出：[0,-1,-1,-1,-1]
解释：这个例子中 1 一开始在位置 0 处，所以此下标的答案为 0 。
翻转的子数组长度为 k = 3 ，1 此时在位置 0 处，所以我们可以翻转子数组 [0, 2]，但翻转后的下标 2 在 banned 中，所以不能执行此操作。
由于 1 没法离开位置 0 ，所以其他位置的答案都是 -1 。

示例 3：

输入：n = 4, p = 2, banned = [0,1,3], k = 1
输出：[-1,-1,0,-1]
解释：这个例子中，我们只能对长度为 1 的子数组执行翻转操作，所以 1 无法离开初始位置。

提示：

• 1 <= n <= 10^5
• 0 <= p <= n - 1
• 0 <= banned.length <= n - 1
• 0 <= banned[i] <= n - 1
• 1 <= k <= n 
• banned[i] != p
• banned 中的值 互不相同 。

题解

方法一：

思路

在n个数中，有n-k+1个长度为k子数组。对子数组的反转，若子数组中有1，可以将1移动到子数组中对于的对称点。

一个直观的思路就是广搜，从p点作为出发点。然后枚举所有包含当前点u的k长度子数组，u的对称点就是可以转移的点。问题是这个图的边数是$O(n^2)$的。直接广搜会超时

我们进一步观察到无论k是是奇数还是偶数，能转移的点都是只间隔一个点。所以可以按照奇偶性分成两个未遍历点的有序集合，每次广搜转移通过二分查找找到需要删除的范围，然后从集合中删除这个范围内存在的点。

由于广搜每个点都要二分查找所用时间$O(nlogn)$，每个点只会删除一次，对于删除点可以用平衡树或并查集，时间复杂度也是$O(nlogn)$

代码

//并查集
class Solution {
public:
    vector<int> minReverseOperations(int n, int p, vector<int>& banned, int k) {
        int st[2][n+5];
        memset(st, -1, sizeof(st));
        function<int(int,int)> ufind = [&](int wc, int x) {
            return st[wc][x] < 0 ? x : st[wc][x] = ufind(wc, st[wc][x]);
        };
        auto ujoin = [&](int wc, int x, int y) {
            st[wc][ufind(wc, x)] = ufind(wc, y);
        };
        vector<int> ban(n), uban[2], ans(n, -1);
        for (int i:banned) ban[i] = 1;
        for (int i=0; i<n; i++) {
            if (ban[i] || i == p) continue;
            uban[i%2].push_back(i);
        }
        uban[0].push_back(n);
        uban[1].push_back(n);
        ans[p] = 0;
        queue<int> q;
        q.push(p);
        int stp = 0;
        while (q.size()) {
            int sz = q.size();
            for (int i=0; i<sz; i++) {
                int u = q.front(); q.pop();
                ans[u] = stp;
                int l = max(u-k+1, k-1-u), r = min(u+k-1, 2*n-k-1-u);
                auto& a = uban[l%2];
                int x = ufind(l%2, lower_bound(a.begin(),a.end(), l)-a.begin());
                while (a[x]<=r) {
                    q.push(a[x]);
                    st[l%2][x] = ufind(l%2, x+1);
                    // ujoin(l%2, x, x+1);
                    x = ufind(l%2, x);
                }
            }
            stp++;
        }
        return ans;
    }
};

// 平衡树
class Solution {
public:
    vector<int> minReverseOperations(int n, int p, vector<int>& banned, int k) {
        set<int> st[2];
        for (int i=0; i<n; i++) {
            st[i%2].insert(i);
        }
        st[p%2].erase(p);
        for (int i:banned) st[i%2].erase(i);
        vector<int> ans(n, -1);
        ans[p] = 0;
        queue<int> q;
        q.push(p);
        int stp = 0;
        while (q.size()) {
            stp++;
            int sz = q.size();
            for (int i=0; i<sz; i++) {
                int u = q.front(); q.pop();
                int l = u-k+1, r = u+k-1;
                if (l<0) l = k-1-u;
                if (r>=n) r = 2*n-k-1-u;
                auto itl = st[l%2].lower_bound(l);
                auto itr = st[l%2].upper_bound(r);
                while (itl != itr) {
                    if ((*itl-l)%2) {
                        itl++;
                    } else {
                        q.push(*itl);
                        ans[*itl] = stp;
                        st[l%2].erase(itl++);
                    }
                }
            }
        }
        return ans;
    }
};