Moe's CF Life

喵~ 主人，今天由我来为你讲解一道非常经典的组队问题哦！这道题叫做 "Team Olympiad"，非常适合刚刚接触算法的同学来练练手，巩固一下基础知识呢，的说。

题目大意

这道题是这样的啦：

在一个学校里有 n 个小朋友，每个小朋友都身怀绝技，要么擅长编程（我们用数字 1 代表），要么擅-长数学（用 2 代表），要么擅长体育（用 3 代表）。每个小朋友都只擅长其中一门哦。

现在学校要组织参加一个科学奥林匹克竞赛，要求以三人一组的形式参赛。规定每支队伍都必须由一个编程小能手、一个数学小天才和一个体育小健将组成。当然啦，每个小朋友最多只能参加一个队伍。

主人需要做的就是，计算出最多可以组成多少支这样的队伍，并且把每支队伍的成员都找出来。小朋友们的编号是从 1 到 n 的，要按照输入顺序来哦。

举个例子喵：假如有 7 个小朋友，他们的特长分别是 1 3 1 3 2 1 2。我们可以发现：

编程 (1) 的有：1号, 3号, 6号
数学 (2) 的有：5号, 7号
体育 (3) 的有：2号, 4号

因为数学小朋友只有 2 个，所以最多也只能组 2 支队伍啦。我们可以这样组队：

队伍1: 3号(编程), 5号(数学), 2号(体育)
队伍2: 6号(编程), 7号(数学), 4号(体育)

最后输出队伍数量 2，以及这两支队伍的成员编号就可以啦。

题解方法

这个问题其实非常直观，就像我们分糖果一样，喵~

一支完整的队伍需要「编程」、「数学」、「体育」各一名同学。那么，我们能组建的队伍数量，是不是就取决于人数最少的那一门特长的同学数量呢？这就好比一个木桶，能装多少水取决于最短的那块木板，对吧？

所以，解题的思路就很清晰啦：

分类统计：我们首先需要遍历所有 n 个小朋友，把他们按照特长分成三组。为了方便输出最终的队伍成员，我们不能只统计人数，而是要把每个小朋友的原始编号（从 1 到 n）存起来。
寻找瓶颈：我们可以用三个列表（在 C++ 中就是 vector）分别存放三类特长小朋友的编号。统计完后，每个列表的大小就代表了该特长的人数。我们取这三个列表中最小的那个尺寸，这个尺寸就是我们能组建的最大队伍数 w。
组建队伍：确定了最大队伍数 w 之后，我们就可以开始组队了。因为每个列表里的编号都是现成的，我们只需要从每个列表中按顺序各取一个编号，就能组成一支队伍。比如，取三个列表的第 1 个编号组成第 1 队，第 2 个编号组成第 2 队……一直到第 w 队。

这样一来，问题就迎刃而解啦，是不是很简单呢，喵~

题解代码

下面是这道题的 C++ 实现代码，我已经加上了详细的注释，方便主人理解每一行代码的作用哦。

cpp

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    // 这两行是为了加速 C++ 的输入输出，在处理大量数据时很有用，是个好习惯喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    // 首先，读取小朋友的总数 n
    int n;
    std::cin >> n;

    // 创建三个 vector 容器，就像三个篮子，分别用来存放三类特长小朋友的编号
    // 编号是 1-based 的哦
    std::vector<int> programmers;     // 存放编程(1)小朋友的编号
    std::vector<int> mathematicians;  // 存放数学(2)小朋友的编号
    std::vector<int> pe_specialists;  // 存放体育(3)小朋友的编号

    // 循环 n 次，读取每个小朋友的特长并进行分类
    // 这里的循环变量 i 直接从 1 开始，正好对应小朋友的 1-based 编号，很方便！
    for (int i = 1; i <= n; ++i) {
        int t; // 用来存储当前小朋友的特长类型
        std::cin >> t;

        // 根据特长 t，把小朋友的编号 i 放入对应的 vector 中
        if (t == 1) {
            programmers.push_back(i);
        } else if (t == 2) {
            mathematicians.push_back(i);
        } else { // t 如果不是 1 或 2，那就肯定是 3 啦
            pe_specialists.push_back(i);
        }
    }

    // 计算能组成的最大队伍数 w
    // w 等于三个 vector 中尺寸最小的那个，这就是我们的“短板”
    // std::min 加上 {} 初始化列表，可以方便地找出多个数的最小值
    size_t w = std::min({programmers.size(), mathematicians.size(), pe_specialists.size()});

    // 先输出最大队伍数 w
    std::cout << w << '\n';

    // 循环 w 次，来组建并输出每一支队伍
    // 第 i 支队伍由第 i 个编程、第 i 个数学和第 i 个体育小朋友组成
    for (size_t i = 0; i < w; ++i) {
        // 输出三个小朋友的编号，用空格隔开
        // 因为 vector 的下标是从 0 开始的，所以我们用 i 来访问
        std::cout << programmers[i] << " " << mathematicians[i] << " " << pe_specialists[i] << '\n';
    }

    // 程序顺利结束，返回 0
    return 0;
}

知识点介绍

这道题虽然简单，但里面用到的一些 C++ 特性还是很有用的，我们来一起学习一下吧，喵！

std::vector 容器std::vector 是 C++ 标准库里的一个非常有用的动态数组。它和普通数组不一样，大小是可以在运行时改变的。
- #include <vector>：使用它需要包含这个头文件。
- programmers.push_back(i)：这是 vector 最常用的操作之一，可以在末尾添加一个元素。在这个题里，我们用它来收集各个特长的小朋友编号。
- programmers.size()：这个函数返回 vector 中元素的数量。我们用它来确定每种特长的人数。
- programmers[i]：通过下标访问元素，和普通数组一样。要注意下标是从 0 开始的哦。 vector 非常适合用在像本题这样，事先不知道需要存储多少个元素的场景。
std::min 函数std::min 来自于 <algorithm> 头文件，顾名思义就是用来求最小值的。
- 在 C++11 标准之后，std::min 可以接受一个初始化列表（initializer list），像这样 std::min({a, b, c, ...})，这让我们求多个数的最小值变得异常方便，一行代码就能搞定！
C++ 快速 I/O 在一些算法竞赛中，输入输出的数据量可能非常大，导致 cin 和 cout 变慢。代码开头的两行就是为了解决这个问题：
- std::ios_base::sync_with_stdio(false);：它会解除 C++ 的 iostream 和 C 的 stdio 之间的同步。默认情况下，它们是同步的，这会带来一些性能开销。
- std::cin.tie(NULL);：它会解除 cin 和 cout 的绑定。默认情况下，每次 cin 读取之前，都会先刷新 cout 的缓冲区。解除绑定后，就不需要等待 cout 刷新了。对于这道题 n <= 5000 的数据量来说，这两行可能不是必须的，但养成这个好习惯对以后解决更复杂的问题非常有帮助哦！

好啦，今天的讲解就到这里啦！希望主人有所收获，喵~ 如果还有其他问题，随时可以再来找我哦！

题目大意 ​

题解方法 ​

题解代码 ​

知识点介绍 ​

题目大意

题解方法

题解代码

知识点介绍