Leetcode1521 找到最接近目标的函数值 位运算

Leetcode1521 找到最接近目标的函数值 位运算

题意

给定(n)个数，目标数(target),求区间([l,r])，(a_l & a_{l+1} & ...a_{r-1}&a_r = f),(|f - target|)的最小值

[1 leq n leq 10^5\ 1 leq a_i leq 1e9\ 0 leq target leq 1e7 ]

分析

显然线段树或者ST表二分可做。

但是此题也可利用与运算的性质：

注意如果固定(r)，那么枚举(l)，最多会产生(20)个(f)，这是因为与运算使其单调递减，且每次变化会至少少一个(1)，那么只需要动态维护这个集合，从(r)，到(r+1)的过程，只需要让(a_{r+1})和集合中的数做与运算即可，同时维护最小值。

用vector表示集合复杂度(O(nlogn)),set维护起来方便，复杂度(O(nlognlog(logn)))

代码

class Solution {
public:
    int closestToTarget(vector<int>& arr, int target) {
        set<int> st;
        int ans = 1e9;
        for(int i = 0;i < arr.size();i++){
            for(auto it:st){
                ans = min(ans,abs(target - (arr[i] & it)));
            }
            set<int> Newst;
            for(auto it:st){
                Newst.insert(arr[i] & it);
            }
            Newst.insert(arr[i]);
            ans = min(ans,abs(target - arr[i]));
            st = Newst;
        }
        return ans;
    }
};