100040. 让所有学生保持开心的分组方法数

100040.让所有学生保持开心的分组方法数

题目描述：

给你一个下标从 0 开始、长度为 n 的整数数组 nums ，其中 n 是班级中学生的总数。班主任希望能够在让所有学生保持开心的情况下选出一组学生：

如果能够满足下述两个条件之一，则认为第 i 位学生将会保持开心：

• 这位学生被选中，并且被选中的学生人数 严格大于 nums[i] 。
• 这位学生没有被选中，并且被选中的学生人数 严格小于 nums[i] 。

返回能够满足让所有学生保持开心的分组方法的数目。

数据范围：

$1\le nums.len \le 10^5;0\le nums[i] \lt nums.len$

题解：

假设选中了 $k$ 个人，那么会有 $n - k$ 个没有被选中的，也就是有 $n - k$ 个数严格大于 $k$ ，有 $k$ 个数严格小于 $k$ 。

因此选出 $k$ 个人其实是唯一的，因为不可能有数即严格大于 $k$ ，又严格小于 $k$ 。

这样的话就可以考虑选哪 $k$ 个人。因为有一部分要严格大于 $k$ ，一部分严格小于 $k$ 。所以可以考虑直接排序，从前往后贪心的选择。

代码：

auto optimize_cpp_stdio = []()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution
{
public:
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const int INF = 0x3f3f3f3f;
    int countWays(vector<int> &nums)
    {
        int n = nums.size();
        int cnt = 0;
        int ans = 0;
        sort(nums.begin(), nums.end());
        int last = -1;
        int pre = -1;
        if (cnt < nums[0])
            ans++;
        for (int i = 0; i < n; ++i)
        {
            // 这里可以写成 i + 1 == n或上另一个条件，
            // 如果 i + 1 == n就会走前面直接返回 true，不会判断后面就不会越界
            if(cnt + 1 > nums[i] && (i + 1  == n || cnt + 1 < nums[i + 1]))
            {
                ans++;
            }
            cnt++;
        }
        return ans;
    }
};