Problem: 1655. 分配重复整数-Distribute Repeating Integers
计算得到nums数字的频次，排序的，quantity倒序排序的，tr顺序排序，若tr.back() >=sum(quantity)表示一定可行，若sum(quantity) > sum(tr)表示一定不行，若quantity.back() > tr.back()也表示不行
status表示被用掉的quantity，对每个tr[i]，从大到小找到使得tr[i] - sum(quantity[i] + quantity[j] + quantity[k] + …)最小的i, j, k等等，用状态数组status标记
优先使用tr[i]完全等于quantity[j]的i、j数对
最后检查是否存在quantity没有被分配出去
Code
class Solution { public: vector<bool> status, cp; int mi; void dfs(vector<int>& quan, int num) { if(num < 0) { return; } else { if(mi > num) { mi = num; cp = status; } } unordered_set<int> te; for(int i = 0; i < quan.size(); i++) { if(te.find(quan[i])!=te.end()) continue; if(status[i] ==false && quan[i] <= num) { te.insert(quan[i]); status[i] = true; dfs(quan, num - quan[i]); status[i] = false; } } } bool canDistribute(vector<int>& nums, vector<int>& quantity) { unordered_map<int, int> mp; for(int& i : nums) mp[i]++; int sum = 0, s2 = 0; for(int& i : quantity) sum += i; vector<int> tr; for(auto&& [k, l] : mp) tr.push_back(l); sort(tr.begin(), tr.end()); sort(quantity.begin(), quantity.end(), greater<int>()); for(int& i : tr) s2 += i; if(tr.back() >= sum) return true; if(sum > s2) return false; if(quantity.back() > tr.back()) return false; int m = tr.size(), n = quantity.size(), a; status.assign(n, false); cp = status; for(int i = 0; i < m; i++) { status = cp; mi = INT_MAX; dfs(quantity, tr[i]); } for(int i = 0; i < n; i++) { if(cp[i] == false) { return false; } } return true; } };
