Day7力扣打卡

打卡记录

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

链接

举例说明，假设 $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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

做菜顺序（递推）

链接

从大到小排序，得到递推公式：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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13