E30930:猫猫水群聊

http://cs101.openjudge.cn/practice/30930/

猫猫爱水群。

猫猫每天都会统计群里面每个群友发言数量 $x_{i}$ 。有一天猫猫突发奇想，想统计一下 x 的” $h 因子$ ”作为群聊的活跃度。定义 $S_{k}$ 为 $f_{i} \geq k$ 的 $f_{i}$ 数量，那么 $h 因子$ 就是 $S_{k} \geq k$ 的最大的 k。猫猫需要求出群聊的活跃度。即：

如果有至少 k 个群友，他们每个人的发言数量都不少于 k 条，那么满足这一条件的最大的 k 值，就是该群聊的 h 因子。

举例：假设群友发言数排序后为：[10, 8, 5, 2, 1]。

尝试 k = 3：有 3 个人的发言数（10, 8, 5）都大于或等于 3，满足条件。
尝试 k = 4：只有 3 个人的发言数大于或等于 4，不满足“至少有 4 个人”的要求。因此，满足条件的最大 k值为 3，群聊活跃度为 3。

输入

第一行包含一个整数 n（1 <= n <= 5 * 10^5），表示群友数量。

接下来一行，包含 n 个整数 xi (0 <= xi <= 10^9)，表示第 i 个群友当天发言数量。

输出

输出一行，表示群聊的活跃度。

样例输入

22
262 128 210 223 62 70 104 61 80 44 40 6 63 94 42 18 1 13 0 0 0 0

样例输出

提示：共 50 个测试点，总输入数据不超过 70 MB。

来源：2026 spring, RainFestival

这是一个经典的“H指数（H-Index）”问题。

解题思路

要计算最大满足 $S_{k} \geq k$ 的 $k$ 值，我们可以采取以下步骤：

将所有群友的发言数量 $x$ 从大到小（降序） 进行排序。
排序后，对于第 $i$ 个元素（下标从 0 开始），它表示有 $i + 1$ 个人的发言数量都大于或等于 $x [i]$ 。
遍历排序后的数组，如果当前的发言数 $x [i] \geq i + 1$ ，说明可以满足 $k = i + 1$ 的条件。
一旦遇到 $x [i] < i + 1$ ，说明无法满足更长的长度，此时最大满足条件的 $k$ 即为 $i$ ，我们可以直接结束遍历并输出结果。

由于群友数量 $n$ 最大为 $5 \times 10^{5}$ ，在 Python 中，使用内置的 sort() 方法可以在 $O (n \log n)$ 的时间复杂度内完成排序，能够较好地满足时限要求。

Python 代码实现

可以使用以下代码解决该问题。为了保证在大数据量下的输入效率，这里使用了 sys.stdin.read：

python

import sys

def solve():
    # 一次性读取所有输入，提升读取效率
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n = int(input_data[0])
    # 将发言数转换为整数列表
    x = [int(v) for v in input_data[1:n+1]]
    
    # 将发言数量从大到小排序
    x.sort(reverse=True)
    
    h_index = 0
    # 遍历排序后的数组，寻找最大的满足条件的 k
    for i in range(n):
        if x[i] >= i + 1:
            h_index = i + 1
        else:
            break
            
    print(h_index)

if __name__ == '__main__':
    solve()

复杂度分析

时间复杂度： $O (n \log n)$ ，主要的时间开销在对长度为 $n$ 的数组进行排序，后续的单次遍历时间复杂度为 $O (n)$ 。
空间复杂度： $O (n)$ ，用于存储输入的发言数量列表。

E30930:猫猫水群聊 ​

E30930:猫猫水群聊