第 122 场 LeetCode 双周赛题解

A 将数组分成最小总代价的子数组 I

枚举：枚举后两个子数组的起始下标

class Solution {
public:
    int minimumCost(vector<int> &nums) {
        int n = nums.size();
        int res = INT32_MAX;
        for (int i = 1; i < n; i++)
            for (int j = i + 1; j < n; j++)
                res = min(res, nums[0] + nums[i] + nums[j]);
        return res;
    }
};

---

B 判断一个数组是否可以变为有序

模拟：模拟冒泡排序的过程，若相邻元素大小关系需要交换位置，但其二进制下数位为 1 的数目不同，则返回false，若完成排序返回true

class Solution {
public:
    bool canSortArray(vector<int> &nums) {
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n - 1; j++) {
                if (nums[j] <= nums[j + 1])
                    continue;
                if (popcnt(nums[j]) != popcnt(nums[j + 1]))
                    return false;
                swap(nums[j], nums[j + 1]);
            }
        }
        return true;
    }

    int popcnt(int x) {//x的二进制下数位为1的数目 
        int res = 0;
        for (int i = 0; i < 9; i++)
            if (x >> i & 1)
                res++;
        return res;
    }
};

---

C 通过操作使数组长度最小

脑筋急转弯：设 $nums$ 中最小元素为 x，1）若存在 y 使得 y%x $\ne$ 0 ，则可以通过y%x将其余所有元素删除，最终答案为 1 ；2）否则用 x 可以将所有其他元素删除，然后最后只剩所有的 x ，此时最后数组的最小长度为 $?\frac{count(x)}{2}?$

class Solution {
public:
    int minimumArrayLength(vector<int> &nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        for (int i = 1; i < n; i++)
            if (nums[i] % nums[0] != 0)
                return 1;
        return (count(nums.begin(), nums.end(), nums[0]) + 1) / 2;
    }
};

---

D 将数组分成最小总代价的子数组 II

滑动窗口+堆+哈希表：枚举第 $k$ 个子数组的开始下标 $i$ ，此时 $k$ 个子数组的最小代价为 $nums[0]+nums[i]+s$ ，$s$ 为 $nums[i?dist,i?1]$ 中最小的 $k?2$ 个元素之和，通过枚举 $i$ ，然后通过两个堆和两个哈希表维护 $s$

class Solution {
public:
    using ll = long long;

    long long minimumCost(vector<int> &nums, int k, int dist) {
        int n = nums.size();
        priority_queue<int, vector<int>, greater<int>> out;//最大堆，在nums[i-dist,i-1]范围内，不在最小的k-2个之内
        priority_queue<int> sel;//最小堆，在nums[i-dist,i-1]范围内，且在最小的k-2个之内
        unordered_map<int, int> cs, co;//cs: sel中对应元素的数目，co：out中对应元素的数目
        ll s = 0;
        for (int i = 1; i <= k - 2; i++) {//初始化sel，cs
            s += nums[i];
            sel.push(nums[i]);
            cs[nums[i]]++;
        }
        ll res = INT64_MAX;
        for (int i = k - 1; i < n; i++) {//枚举i
            if (int pre = i - dist - 1;pre >= 1) {//滑动窗口右移，即nums[pre]移出窗口
                while (cs[sel.top()] == 0)//更新sel
                    sel.pop();
                if (nums[pre] <= sel.top()) {//需要更新sel和out
                    cs[nums[pre]]--;
                    s -= nums[pre];
                    while (co[out.top()] == 0)//更新out
                        out.pop();
                    s += out.top();
                    sel.push(out.top());
                    cs[out.top()]++;
                    co[out.top()]--;
                    out.pop();
                } else//只需更新co
                    co[nums[pre]]--;

            }
            res = min(res, nums[0] + s + nums[i]);
            out.push(nums[i]);
            co[nums[i]]++;
            while (cs[sel.top()] == 0)
                sel.pop();
            while (co[out.top()] == 0)
                out.pop();
            if (!out.empty() && sel.top() > out.top()) {//需要更新sel和out
                int mx = sel.top();
                int mn = out.top();
                cs[mx]--;
                cs[mn]++;
                co[mn]--;
                co[mx]++;
                s -= mx;
                s += mn;
                sel.pop();
                sel.push(mn);
                out.pop();
                out.push(mx);
            }
        }
        return res;
    }
};