Ad-Hoc问题：分析特定问题的独有性质

摘要: 分析问题的性质

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

在通信网络中，有一类称为 Ad-hoc 网络。ad-hoc网络是一种特殊的网络模式，它允许一组设备（如计算机、手机等）通过无线方式相互连接，而不需要依赖固定的基础设施，如路由器或交换机。这种网络模式通常用于特定的目的或场景，并且能够快速部署，因此可以视为一种临时网络。

在算法问题中，有一些问题无法套用现成的算法，也没有模式化的求解方法，而是需要通过分析问题和数据，自己设计算法来解决问题，这类问题就称作 Ad-Hoc 类问题，也被称为杂题。这里 Ad-Hoc 的含义也是强调解决方案是临时的，是针对特定场景定制的，不具备普适性和推广性。

总结一下，Ad-Hoc 类问题比较考验知识基础和创造性思维，需要临场分析问题和数据，发现特定问题的独有性质，进而设计出算法。

题目

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

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

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

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

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

提示：

1 <= nums.length <= 1e5
0 <= nums[i] < nums.length

示例 1：
输入：nums = [1,1]
输出：2
解释：
有两种可行的方法：
班主任没有选中学生。
班主任选中所有学生形成一组。
如果班主任仅选中一个学生来完成分组，那么两个学生都无法保持开心。因此，仅存在两种可行的方法。

示例 2：
输入：nums = [6,0,3,3,6,7,2,7]
输出：3
解释：
存在三种可行的方法：
班主任选中下标为 1 的学生形成一组。
班主任选中下标为 1、2、3、6 的学生形成一组。
班主任选中所有学生形成一组。

题解

算法：发现独有性质

本题的关键是通过分析例子，发现重要的性质。

假如某个元素 $nums[i]$ 选了，由限制条件1，那么选出的个数 $c$ 必须满足 $c > nums[i]$，进一步地，所有不大于 $nums[i]$ 的元素也必须选。

因为如果 $nums[j] < nums[i]$，且 $nums[j]$ 没选，那么由限制条件2，$c < nums[j]$，与前面的 $c > nums[i]$ 矛盾。

只要发现以上性质，就可以给出解决问题的算法：

首先对 $nums$ 排序，然后依次枚举选出的元素个数 $c$，如果 $nums[c - 1] < c$ 且 $bums[c] > c$，则选择 $nums[0],\cdots, nums[c-1]$ 是一种可行的方案。

$c = 0$ 和 $c = n$ 是边界情况，可以单独判断。

代码 (Python)

class Solution:
    def countWays(self, nums: List[int]) -> int:
        nums.sort()
        n = len(nums)
        ans = 0
        if 0 < nums[0]:
            ans += 1
        for c in range(1, n):
            if nums[c - 1] < c and nums[c] > c:
                ans += 1
        if nums[n - 1] < n:
            ans += 1
        return ans

---