题目描述

新生Freddie选了 $k$ 门课程，每个课程类别要求至少选 $r$ 门该类别的课程。需判断Freddie的选课是否满足所有类别要求。

解题思路

1. 问题分析：

   • 每个课程类别包含若干课程，Freddie的选课中需至少包含该类别要求的 $r$ 门课程。
   • 同一课程可能属于多个类别，但每个类别内的课程编号唯一。

2. 算法思路：

   • 标记选课：使用布尔数组 mark 标记Freddie选的所有课程。
   • 类别检查：对每个类别，统计Freddie选的课程中属于该类别的数量。若该数量小于类别要求的 $r$，则不满足毕业条件。
   • 去重处理：同一课程在类别中只计数一次（尽管题目保证类别内课程唯一，代码中仍通过 vis 数组确保准确性）。

代码解释

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

int main() {
    int k, m;
    bool vis[10000]; // 临时标记类别内已统计的课程
    bool mark[10000]; // 标记Freddie选的所有课程
    int b;

    while (scanf("%d", &k) && k) { // 输入k，若k=0则结束
        scanf("%d", &m);
        memset(mark, 0, sizeof(mark)); // 初始化选课标记

        // 读取Freddie选的k门课程
        for (int i = 1; i <= k; i++) {
            scanf("%d", &b);
            mark[b] = true; // 标记选课
        }

        int c, r, a, count, flag = 0; // flag记录是否不满足条件
        for (int i = 1; i <= m; i++) {
            count = 0;
            memset(vis, 0, sizeof(vis)); // 初始化类别内课程标记

            scanf("%d%d", &c, &r); // 读取类别信息：c门课程，至少选r门
            for (int j = 1; j <= c; j++) {
                scanf("%d", &a);
                // 若课程被Freddie选中且未在该类别中统计过
                if (mark[a] && !vis[a]) { 
                    count++;
                    vis[a] = true; // 标记已统计，避免重复计数
                }
            }
            if (count < r) { // 不满足类别要求
                flag = 1;
            }
        }
        // 输出结果
        printf("%s\n", flag ? "no" : "yes");
    }
    return 0;
}

注意事项

1. 数据结构选择：

   • 使用布尔数组 mark 标记选课，索引为课程编号（4位整数，范围0~9999，数组大小足够）。
   • vis 数组确保同一课程在类别中仅计数一次（尽管题目保证类别内课程唯一，此操作增强鲁棒性）。

2. 输入处理：

   • 输入可能包含多行课程，scanf 自动处理空格和换行，正确读取所有课程。
   • 当 $m = 0$ 时（无类别要求），直接输出 "yes"，符合题意。

3. 边界条件：

   • 课程编号为4位整数，需确保数组索引不越界（代码中使用 10000 大小的数组，覆盖0~9999）。
   • 当所有类别均满足 $\text{count} \geq r$ 时，输出 "yes"，否则 "no"。

复杂度分析

• 时间复杂度：$O(k + \sum c)$，其中 $k$ 为选课数，$c$ 为每个类别的课程数。最坏情况下，总课程数为 $k + m \times c = 100 + 100 \times 100 = 10100$，完全满足性能要求。
• 空间复杂度：$O(1)$，使用固定大小的布尔数组，空间占用恒定。

该算法通过标记和统计高效判断每个类别的选课情况，确保正确性和高效性。