打卡记录

合法分组的最少组数（贪心）

链接

举例说明，假设 $cnt[x]=32$，$k=10$，那么 $32=10+10+10+2$，多出的 $2$ 可以分成两个 $1$，加到两个 $10$ 中，从而得到 $11,11,10$ 三组。通过 $cnt[x]/k$ 与 $cnt[x]$ 之间的大小关系，从而来判断当前是否可以用 $k$ 为最小的组元素个数来分组，如果不行的话，让 $k$ 数值减少，然后再次判断。如果可以分组，则当前组 $cnt[x]$ 可以分成 $\lceil \frac{cnt[x]}{k+1}\rceil$ 个组。

$\lceil \frac{cnt[x]}{k+1}\rceil$ 可以由 k = 10，30…33 这样推出

class Solution {
public:int minGroupsForValidAssignment(vector<int>& nums) {unordered_map<int, int> hash;for (int& num : nums) hash[num]++;int k = min_element(hash.begin(), hash.end(), [&](const auto& a, const auto& b) {return a.second < b.second;})->second;int ans = 0;while (!ans) {for (auto& [_, x] : hash) {if (x / k < x % k) {ans = 0;break;}ans += (x + k) / (k + 1);}k--;}return ans;}
};

做菜顺序（递推）

链接

从大到小排序，得到递推公式：f(k)=f(k−1)+(a[0]+a[1]+⋯+a[k−1])

例如，做 k=1,2,3 道菜时。

k=1 时，总和为 f(1)=a[0]。
k=2 时，总和为 f(2)=2⋅a[0]+a[1]。
k=3 时，总和为 f(3)=3⋅a[0]+2⋅a[1]+a[2]。

class Solution {
public:int maxSatisfaction(vector<int>& satisfaction) {sort(satisfaction.begin(), satisfaction.end(), greater<int>());int n = satisfaction.size(), sum = 0, f = 0;for (int i = 0; i < n; ++i) {sum += satisfaction[i];if (sum <= 0) break;f += sum;}return f;}
};