读题

从 n 道题中选 m 道组成题单，签到题是题单中难度最低的所有题

目标：最大化签到题的数量

解题思路

若题单中最低难度为d，则签到题数量是难度d的题数（记为a[d]），且需满足 “难度≥d 的题总数≥m”（才能选出 m 道题）。

步骤：

用数组a统计每个难度的题数（a[d]表示难度d的题有多少道）。

从最大难度n往最小难度1遍历，累加 “难度≥当前 i” 的总题数p。

当p≥m时，说明可以选 m 道题且最低难度为i，此时签到题数量为a[i]，记录这些a[i]的最大值。

最终答案是 “最大的a[i]” 和 “m” 的较小值（因为若a[i]≥m，最多只能选 m 道作为签到题）。

#include<stdio.h>
#define MAXN 200010  // 题目中a_i≤n，n≤2e5，数组大小足够
int main() {
    int n, m, k;
    int a[MAXN] = {0};  // 初始化数组，a[d]记录难度d的题数
    int p = 0;  // 累计"难度≥当前i"的总题数
    int ans = 0;  // 记录最大的签到题数量
    // 读入n和m
    scanf("%d %d", &n, &m);

    // 统计每个难度的题数
    for (int i = 1; i <= n; i++) {
        scanf("%d", &k);
        a[k]++;  // 难度k的题数+1
    }

    // 从最大难度往最小难度遍历
    for (int i = n; i >= 1; i--)
    {
        p += a[i];  // 累加当前难度i的题数（p变为"难度≥i"的总题数）
        // 若p≥m，说明能选m道题且最低难度为i，更新ans
        if (p >= m)
        {
            // 取当前a[i]和已有ans的最大值
            if (a[i] > ans) {ans = a[i];}
        }
    }
    // 最大的a[i]不能超过m（因为最多选m道题）
    if (ans > m){ans = m;}
    printf("%d\n", ans);
    return 0;
}