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;
    }
};

LeetCode-2870 Minimum Number of Operations to Make Array Empty