LeetCode-2870 Minimum Number of Operations to Make Array Empty

Description

给定一个长为\(n\)的数组\(a\)，提供2种操作：

选择2个相同元素并消去。
选择3个相同元素并消去。

求最小操作次数，使得数组为空。若不存在方案则返回\(-1\)。

Constraints

\(1 \le n \le 10^5\)
\(1 \le a_i \le 10^6\)

Solution

先观察一下：

2和3互质，公倍数是6。
每组相同元素独立统计（因为下标无关）。
只要频率不是1，那么必然有解（因为2和3包含了奇数和偶数）。

再转换题意：一个数的出现频率可构造为\(i \times 2 + j \times 3\)，求最小的\(i+j\)。

当我尝试贪心的馊主意时就蛋疼了：

能不能贪心的全部抠掉3再抠2？一个反例是4，先抠3就无解，而抠两个2才是正解。
那我抠6的倍数？仍存在fvcking的反例13，使得余1。

然后我生气了，正着不行就反过来吧。根据结论3。当余1时：用2补成一个3，或者用3补成两个2。

Code

class Solution {
public:
    int minOperations(vector<int>& nums) {
        using umap = unordered_map<int, int>;
        umap cnts, rcnts;
        for(auto v : nums) cnts[v]++;
        for(auto [_, n] : cnts) rcnts[n]++;
        if(rcnts.count(1)) return -1;
        int ans = 0;
        for(auto [n_const, c] : rcnts) {
            int t = 0;
            int n = n_const;

            int _2 = 0;
            int _3 = 0;

            if(n >= 3) {
                _3 = n / 3;
                n -= _3 * 3;
                t += _3;
            }

            if(n >= 2) {
                _2 = n / 2;
                n -= _2 * 2;
                t += _2;
            }

            if(n == 1) {
                t += !_2;
            }

            ans += t * c;
        }
        return ans;
    }
};

Link

LeetCode-2870 Minimum Number of Operations to Make Array Empty