低水平选手的自我救赎 （1）CLRS Exercise 16.5-2

题目大意

给定正整数 $n$ 和一个由 $m$ 个正整数构成的可重集合 $A$，满足 $\forall a\in A,?a\le n$ 且 $m\le n$ 。
定义 $N_t(A) = |\{a\in A\colon a\le t\}|$ 。请在 $O(m)$ 的时间内判断 $\forall t = 0, 2, \dots, n,?N_t(A)\le t$ 是否成立。
多组询问。

解法

用一个长为 $n$ 的数组 $\mathrm{cnt}[1..n]$ 记录集合 $A$ 中每个数出现的次数，若存在 $a\in A,?\mathrm{cnt}[a]>a$ 则结论不成立，否则成立。

这解法是错的。来源
反例：$A=\{1,2,2\},?n=3$
（我要给 Solution Author 发邮件！）

正解在此

对于 $t \ge m$，$N_t(A)\le m \le t$ 自然成立。
只需考虑对 $t < m$ 是否有 $N_t(A)\le t$ 。

统计前缀和判断一下即可，复杂度 $O(m)$ 。

总结

1. 这道题真的没那么简单
2. 我的水平确实低（真心的）
3. 我要仔细读读 CLRS
4. 把自己当做小学生！