题目描述

在一个有 $n$ 个人的班级中，共有 $m$ 项不同的技能。对于第 $i$ 项技能（$1 \le i \le m$），已知有 $k_i$ 个人掌握了这项技能。

我们需要计算，至少有多少个人掌握了 全部 $m$ 项技能。

样例

输入:
50 4
30 35 42 46

输出:
3

说明：全班 50 人，4 项技能。会各项技能的人数分别为 30, 35, 42, 46。问至少有多少人 4 项都会。答案是 3。

算法 (数学推导 / 容斥原理思想)

时间复杂度：$O(m)$

思路分析

这个问题可以从不同的角度思考，但最终都指向同一个结论。

思路一：从 “技能点” 的角度 (类似题目中的回帖思路)

1. 总技能点: 我们可以把每个人掌握一项技能看作拥有一个“技能点”。全班总共拥有的技能点数量是所有技能掌握人数的总和：
   $$S = \sum_{i=1}^{m} k_i$$
2. 技能点上限: 每个人最多只能掌握 $m$ 项技能。
3. 考虑反面: 假设我们想让掌握全部 $m$ 项技能的人数尽可能少。这意味着我们要让那些不掌握全部技能的人尽可能多地掌握技能。
4. 设 $x$ 是掌握全部 $m$ 项技能的人数。
5. 设 $y = n - x$ 是不掌握全部 $m$ 项技能的人数（即最多掌握 $m-1$ 项技能）。
6. 全班的总技能点 $S$ 由这两部分人贡献：
   • $x$ 个人每人贡献 $m$ 个技能点，总共 $x \times m$ 个。
   • $y$ 个人每人最多贡献 $m-1$ 个技能点，他们贡献的技能点总数至多为 $y \times (m-1)$。
7. 因此，我们有一个不等式关系：
   $$S = (\text{x个人的技能点}) + (\text{y个人的技能点}) \le x \cdot m + y \cdot (m-1)$$
8. 将 $y = n - x$ 代入不等式：
   $$S \le x \cdot m + (n - x) \cdot (m - 1)$$
   $$S \le xm + nm - n - xm + x$$
   $$S \le n(m - 1) + x$$
9. 移项得到 $x$ 的下界：
   $$x \ge S - n(m - 1)$$
10. 考虑非负性: 人数 $x$ 不能是负数。所以，最终的下界是：
    $$x \ge \max(0, S - n(m - 1))$$
    这就是至少掌握全部 $m$ 项技能的人数。

思路二：从集合和补集的角度

1. 设 $P$ 为全班 $n$ 个人的集合。
2. 设 $S_i$ 为掌握第 $i$ 项技能的人的集合，则 $|S_i| = k_i$。
3. 我们要求的是掌握所有技能的人数，即交集的大小 $|S_1 \cap S_2 \cap \dots \cap S_m|$ 的最小值。
4. 考虑补集：设 $S_i^c = P \setminus S_i$ 为不掌握第 $i$ 项技能的人的集合。则 $|S_i^c| = n - k_i$。
5. 设 $A = S_1 \cap S_2 \cap \dots \cap S_m$ 为我们要求的集合（掌握所有技能的人）。
6. 考虑 $A$ 的补集 $A^c = P \setminus A$。$A^c$ 表示至少不掌握一项技能的人的集合。
7. 根据德摩根定律：
   $$A^c = (S_1 \cap S_2 \cap \dots \cap S_m)^c = S_1^c \cup S_2^c \cup \dots \cup S_m^c$$
8. 我们知道，集合的并集大小小于等于各个集合大小之和（这是容斥原理最简单的不等式形式）：
   $$|A^c| = |S_1^c \cup S_2^c \cup \dots \cup S_m^c| \le \sum_{i=1}^{m} |S_i^c|$$
9. 代入 $|S_i^c| = n - k_i$：
   $$|A^c| \le \sum_{i=1}^{m} (n - k_i) = n \cdot m - \sum_{i=1}^{m} k_i = nm - S$$
10. 我们要求的是 $|A|$ 的最小值。因为 $|A| = n - |A^c|$，要最小化 $|A|$，需要最大化 $|A^c|$。$|A^c|$ 的最大值可能是 $nm - S$。
11. 所以，我们得到 $|A|$ 的一个下界：
    $$|A| = n - |A^c| \ge n - (nm - S)$$
    $$|A| \ge n - nm + S$$
    $$|A| \ge S - n(m - 1)$$
12. 同样地，考虑到人数不能为负，最终下界为：
    $$\min |A| = \max(0, S - n(m - 1))$$

两种思路得到了相同的结果。这个结果的直观意义是：总技能点 $S$ 减去 $n$ 个人每人掌握 $m-1$ 项技能所能达到的最大技能点 $n(m-1)$，剩下的“超额”技能点必须由那些掌握全部 $m$ 项技能的人来提供，每个人提供 1 个超额点（从 $m-1$ 到 $m$），所以超额技能点的数量就是掌握全部技能人数的下限。

时间复杂度

1. 读取输入 $n, m$：$O(1)$。
2. 读取 $m$ 个技能人数 $k_i$：$O(m)$。
3. 计算总和 $S = \sum k_i$：$O(m)$。
4. 计算最终结果 $\max(0, S - n(m-1))$：$O(1)$。
5. 总时间复杂度为 $O(m)$。

C++ 代码

#include <bits/stdc++.h> // 引入所有标准库

using namespace std;
using i64 = long long; // 定义 i64 为 long long 的别名，以防中间计算溢出

int main() {
    // 关闭 C++ 标准 IO 流与 C stdio 的同步，提高 cin/cout 速度
    ios::sync_with_stdio(false);
    // 解除 cin 和 cout 的绑定，进一步提速
    cin.tie(nullptr);

    int n, m; // n: 全班人数, m: 技能总数
    cin >> n >> m;

    vector<int> a(m); // 存储 m 个技能分别有多少人会
    for (int i = 0; i < m; i ++ ) {
        cin >> a[i]; // 读入每个技能的人数
    }

    // 计算所有技能掌握人数的总和 S = k1 + k2 + ... + km
    // accumulate 来自 <numeric> 头文件
    i64 sum = accumulate(a.begin(), a.end(), 0LL); // 使用 0LL 保证累加和使用 long long 类型

    // 计算至少有多少人 m 项都会
    // 公式为 max(0, S - n * (m - 1))
    // S 是总技能点
    // n * (m - 1) 是 n 个人每人最多会 m-1 项技能时的最大技能点数
    // sum - n * (m - 1) 表示 "超额" 的技能点数，这些必须由会 m 项技能的人贡献
    // 结果与 0 取 max 是因为人数不能为负
    cout << max(0LL, sum - (i64)n * (m - 1)) << "\n"; // 注意将 n 强制转换为 i64 防止乘法溢出

    return 0; // 程序正常结束
}