G. University Classes - 题解

比赛与标签

比赛: 2017-2018 ACM-ICPC, NEERC, Southern Subregional Contest, qualification stage (Online Mirror, ACM-ICPC Rules, Teams Preferred) 标签: implementation 难度: *900

喵喵，题目在说什么呀？

各位同学、各位铲屎官，大家好呀~！这道题其实非常可爱，让本猫娘来给你梳理一下吧！

是这样的：一所大学里有 n 个学生小组。学校的一天有 7 个上课时间段（从 1 到 7）。题目会给我们每个小组在周一的课表，用一个长度为 7 的、由 '0' 和 '1' 组成的字符串表示。

如果第 j 个字符是 '1'，就代表这个小组在第 j 个时间段有课。
如果是 '0'，就说明那个时间段可以去玩耍或者睡觉啦~

我们的任务是，计算出周一这一天，学校最少需要准备多少间教室，才能保证所有小组的课都能正常进行。当然啦，一个教室在一个时间段里只能容纳一个小组上课哦！

简单来说，就是：

输入：先是一个整数 n（小组数量），然后是 n 行，每行一个 7 位的 01 字符串（课表）。
输出：一个整数，表示最少需要的教室数量。

解题思路大揭秘喵~

这道题听起来好像有点复杂，但其实只要抓住核心问题，就会变得超级简单，就像找到猫薄荷一样让人开心呐！

我们需要的教室数量，是由哪个时刻决定的呢？当然是 同一时间上课小组数量最多 的那个时刻啦！

打个比方，就像食堂开饭一样喵~ 食堂需要准备多少个窗口，不是看一天总共有多少人吃饭，而是看午饭高峰期，最多有多少人同时在排队打饭！只要能满足这个高峰期的需求，其他时间肯定也够用啦。

所以，我们的思路就是：

把 7 个时间段分开来看，它们之间是互不影响的。
我们只需要检查 每一个时间段，分别有多少个小组在同时上课。
然后，我们找出这 7 个时间段中，上课小组数量的 最大值。
这个最大值，就是我们最少需要准备的教室数量！因为只要满足了最拥挤时刻的需求，其他任何时刻的教室数量都肯定是足够的。

举个例子，如果在第 3 个时间段有 5 个小组上课，而在其他所有时间段上课的小组都少于 5 个，那么我们至少需要 5 间教室。有了这 5 间教室，第 3 时间段的需求满足了，其他时间段自然也就不在话下啦！

所以，算法就很清晰了：

我们设置一个变量 max_rooms 来记录最大的教室需求，初始为 0。
然后我们遍历 7 个时间段（也就是遍历输入字符串的每一列）。
对于每一个时间段 j，我们再遍历所有 n 个小组，统计在这个时间段 j 有多少小组的课表上是 '1'。
统计完当前时间段 j 的总上课小组数 count 后，就和 max_rooms 比较一下，如果 count 更大，就更新 max_rooms 的值。
7 个时间段都检查完后，max_rooms 里存的就是我们的最终答案啦！是不是很简单呢，喵~

代码实现时间到！

下面就是本猫娘写好的AC代码啦，加了详细的注释，方便你理解每一句都在做什么哦！

cpp

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main() {
    // 读入小组的数量 n
    int n;
    cin >> n;

    // 创建一个 vector 来存储 n 个小组的课表字符串
    vector<string> schedules(n);
    for (int i = 0; i < n; i++) {
        // 循环读入每个小组的课表
        cin >> schedules[i];
    }

    // 初始化需要的最大教室数量为 0
    int max_rooms = 0;

    // 外层循环：遍历 7 个时间段 (从第 0 列到第 6 列)
    for (int j = 0; j < 7; j++) {
        // 初始化当前时间段需要上课的小组数量为 0
        int count = 0;
        
        // 内层循环：遍历 n 个小组
        for (int i = 0; i < n; i++) {
            // 检查第 i 个小组在第 j 个时间段是否有课
            if (schedules[i][j] == '1') {
                // 如果有课，计数器加一
                count++;
            }
        }

        // 检查当前时间段所需的教室数是否比已记录的最大值还大
        if (count > max_rooms) {
            // 如果是，就更新最大值
            max_rooms = count;
        }
    }

    // 所有时间段都检查完毕，输出最终结果
    cout << max_rooms << endl;

    return 0;
}

复杂度分析喵~

时间复杂度: O(N) 的说。这里的 N 是指小组的数量。我们的代码有一个两层嵌套循环，外层循环固定执行 7 次（代表 7 个时间段），内层循环执行 N 次。所以总的操作次数大约是 7 * N。在计算时间复杂度时，常数系数是可以忽略的，所以最终的时间复杂度就是 O(N) 啦！对于 N 最大为 1000 的情况，这是非常快的！
空间复杂度: O(N) 的说。我们用了一个 vector<string> 来存储所有小组的课表。这个 vector 的大小是 n，每个字符串的长度是 7。所以占用的空间大约是 n * 7。同样，忽略常数 7，空间复杂度就是 O(N)。

知识点与总结

这道题虽然简单，但是能帮我们巩固一些非常重要的思想和技巧哦！

“瓶颈”思想: 这道题的核心就是 "瓶颈" 思想喵！一个系统的整体能力，往往取决于它最薄弱、最繁忙的那个环节。在这里，我们需要的总房间数，就取决于那个最 "拥挤" 的时间段。学会找到问题中的瓶颈，是解决很多优化问题的关键！
二维数据处理: 题目给出的数据可以看成一个 n x 7 的二维表格。我们的解法是 "逐列统计"，也就是遍历每一列（时间段），统计该列的特征（'1'的数量），最后再综合所有列的结果。这是处理二维数据时一种非常常见且有效的方法。
问题简化: 把一个看起来复杂的问题（安排所有课表），简化成 7 个独立的小问题（每个时间段需要多少教室），再取其最大值，是解题的重要一步。学会分解问题，会让思路更清晰！

希望本猫娘的讲解对你有帮助呐！如果还有其他问题，随时都可以来问我哦！一起努力，变得更强吧！喵~ >ω<

G. University Classes - 题解 ​

比赛与标签 ​

喵喵，题目在说什么呀？ ​

解题思路大揭秘喵~ ​

代码实现时间到！ ​

复杂度分析喵~ ​

知识点与总结 ​