Moe's CF Life

喵哈喽~ 主人，今天由我，你的专属小猫娘，来为你讲解一道非常经典的贪心算法问题——B. Taxi！这道题就像是帮小猫们安排出门的车辆一样，要用最少的车车把大家都送回家，很有趣的哦，喵~

题目大意

放学后，有 n 个小学生小组要去 Polycarpus 家参加生日派对！每个小组的人数 s_i 是 1 到 4 个人不等。他们决定坐出租车去，但有一个规定：每个小组的成员必须坐在同一辆车里。每辆出租车最多只能坐 4 个人。

那么问题来了，最少需要多少辆出租车才能把所有的小朋友都送到目的地呢？喵？

举个例子：有 5 个小组，人数分别是 1, 2, 4, 3, 3。我们可以这样安排：

一个 4 人小组自己坐一辆车。
一个 3 人小组自己坐一辆车。
另一个 3 人小组自己坐一辆车。
剩下的 1 人小组和 2 人小组可以坐一辆车（1+2=3 < 4）。

这样总共需要 4 辆车，就是最少的啦！

解题思路

这道题的目标是最小化出租车的数量，一看到“最小化”这个词，我们的小脑袋就要往贪心算法上想啦，喵~ 贪心的核心思想就是每一步都做出当前看起来最优的选择。

怎么才算最优呢？当然是让每辆车的空位越少越好！

我们可以按照小组人数从大到小来考虑，这样能优先把最“占地方”的小组安排掉，剩下的零散小组再想办法拼凑起来。

我的贪心策略是这样的，喵~

统计数量：首先，我们先数一数，人数为 1、2、3、4 的小组各有几个。用一个数组 counts 来记录，counts[i] 就表示 i 人小组的数量。
处理 4 人小组：4 人小组最省心啦！他们自己就能坐满一辆车，不需要和任何其他小组拼车。所以，有多少个 4 人小组，就需要多少辆车。安排完后，他们就开开心心地出发啦。 出租车数量 += counts[4]
处理 3 人小组：接下来是 3 人小组。每个 3 人小组都需要一辆车。但是，每辆车还剩下 1 个空位。本着不浪费的原则，我们看看能不能塞一个 1 人小组进去？当然可以！所以，每个 3 人小组都优先带走一个 1 人小组。 出租车数量 += counts[3]counts[1] -= counts[3] （如果 1 人小组不够，那就减到 0 为止）
处理 2 人小组：现在轮到 2 人小组了。两个 2 人小组正好可以拼成 4 个人，完美地坐满一辆车！所以我们把 2 人小组两两配对。 出租车数量 += counts[2] / 2 配对完后，可能会剩下孤零零的一个 2 人小组（如果 counts[2] 是奇数的话）。这个剩下的小组我们先留着，待会和剩下的 1 人小组一起处理。
处理剩余成员：经过上面几步，现在只剩下一些 1 人小组和可能的一个 2 人小组了。我们把他们所有的人数加起来，看看总共还有多少人。然后把这些人塞进新的出租车里。因为每辆车最多坐 4 人，所以需要的车辆数就是 总剩余人数 / 4 向上取整。 剩余人数 = 剩下的 1 人小组人数 + 剩下的 2 人小组人数出租车数量 += (剩余人数 + 3) / 4 （这是一个向上取整的小技巧哦！）

这样一步步下来，所有小朋友都被安排好啦，而且用的车车数量也是最少的！是不是很清晰呢，喵？

题解代码

下面是 C++ 的实现代码，和我刚刚描述的思路一模一样哦~

cpp

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

void solve() {
    int n;
    std::cin >> n;
    
    // 步骤 1: 用一个 vector 来统计各个人数的小组数量
    // counts[i] 表示 i 人小组的数量
    std::vector<int> counts(5, 0);
    for (int i = 0; i < n; ++i) {
        int s;
        std::cin >> s;
        counts[s]++;
    }

    int taxis = 0;

    // 步骤 2: 4人小组直接各占一辆车
    taxis += counts[4];

    // 步骤 3: 3人小组各占一辆车，并尝试带走一个1人小组
    taxis += counts[3];
    // 从1人小组中减去被3人小组带走的数量
    counts[1] = std::max(0, counts[1] - counts[3]);

    // 步骤 4: 2人小组两两配对
    taxis += counts[2] / 2;
    counts[2] %= 2; // 看看是否剩下1个2人小组

    // 步骤 5: 处理所有剩下的成员 (最多1个2人小组和若干1人小组)
    int remaining_people = counts[2] * 2 + counts[1];
    
    // 用向上取整计算剩余成员需要的车辆
    // (a + b - 1) / b 是整数向上取整的常用写法
    if (remaining_people > 0) {
        taxis += (remaining_people + 3) / 4;
    }

    std::cout << taxis << std::endl;
}

int main() {
    // 为了快一点点，让输入输出不打架~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    solve();

    return 0;
}

知识点介绍

这道题虽然简单，但里面包含了一些很实用的知识点哦，喵~

贪心算法 (Greedy Algorithm)
- 核心思想：贪心算法在每一步决策时，都采取当前状态下最好或最优的选择，从而希望能导致全局最好或最优的解。它不从整体最优上加以考虑，所做的仅是在某种意义上的局部最优解。
- 在本题的应用：我们优先处理能最大化利用出租车空间的组合（比如 4 人组，3+1 组合，2+2 组合），这就是一种贪心策略。事实证明，对于这道题，这种局部最优的策略恰好能得到全局最优解。
计数统计 (Frequency Counting)
- 核心思想：当需要处理的数据种类有限时（本题中只有 1, 2, 3, 4 四种小组），使用一个数组或哈希表来统计每种数据出现的次数，是一种非常高效和方便的做法。
- 在本题的应用：我们用 std::vector<int> counts(5, 0); 创建了一个大小为 5 的向量。counts[1] 存 1 人组数量，counts[2] 存 2 人组数量，以此类推。这比遍历原始数据多次要快得多。
向上取整 (Ceiling Division)
- 问题：在编程中，两个整数相除 a / b 会自动向下取整。但有时我们需要向上取整（比如，5 个人坐 4 人车，需要 ceil(5/4) = 2 辆车）。
- 技巧：对于两个正整数 a 和 b，计算 a / b 的向上取整，可以用 (a + b - 1) / b 这个公式来实现。
- 在本题的应用：当计算剩余的人需要多少辆车时，我们用了 (remaining_people + 3) / 4，这里 a 是 remaining_people，b 是 4。完美解决了拼车问题！

好啦~ 这道题的讲解就到这里了喵！希望主人能够喜欢。如果还有其他问题，随时可以再来找我哦！喵~ (ฅ'ω'ฅ)

题目大意 ​

解题思路 ​

题解代码 ​

知识点介绍 ​

题目大意

解题思路

题解代码

知识点介绍