P4790 摘到多少气球（基础）

解题思路

1. 读懂题目：礼堂里高低不一地挂着 N 个气球，M 位同学每人最多摘 2 个气球，摘下的气球归大家共有。同学伸手能达到的高度如果大于等于气球高度，就能摘到它。我们的目标是让摘到的气球总数最多。

2. 打个比方：就像玩"摘果子"游戏。高个子的同学能摘到高处的果子，矮个子同学只能摘低处的果子。要想摘到最多，就要让每个果子尽量被"能摘到它"的人摘走，尤其是那些挂得很高的果子，一定要留给够得着的同学。

3. 关键贪心策略：先把气球按高度从低到高排好队，再把同学按身高从低到高排好队。然后从最高的同学开始，一个个安排他们去摘气球。

4. 为什么从高到矮处理？ 因为挂得最高的气球最难摘到，只有最高的几位同学够得着。如果让矮个子同学先摘，他可能把低处的两个气球摘走，等最高的同学来摘时，低处气球虽然还剩，但高个子同学也只能摘 2 个，一些高的气球反而没人摘，白白浪费。

5. 每个同学怎么挑气球？ 从最高处往低处看，遇到还没被摘走的、自己又够得着的气球，就摘下来，最多摘 2 个。这样每个同学都优先摘走"最难摘的"气球。

6. 看例子：样例中气球排序后是 88,90,100,100,110,130,135,140,150,160，同学是 80,100,110,120。从最高的 120 开始：他摘 110 和 100；110 的同学摘 100 和 90；100 的同学摘 88；80 的同学一个也够不着。一共摘到 2+2+1=5 个，和答案一致。

7. 边界情况：如果所有气球都比所有同学高，就一个也摘不到；如果同学很多而气球很少，能摘多少摘多少；如果气球数量比"同学数×2"还少，那最多就是把所有气球都摘光。

参考代码

// P4790 摘到多少气球：学生从高到矮，每人最多摘2个能摘到的最高气球
#include <iostream>
using namespace std;
int balloon[105];   // 气球的高度
int student[105];   // 学生伸手能达到的高度
bool taken[105];    // 标记气球是否已被摘走

int main() {
    int N, M;
    cin >> N >> M;
    for (int i = 0; i < N; i++) cin >> balloon[i];
    for (int i = 0; i < M; i++) cin >> student[i];
    // 气球高度升序排序（冒泡排序）
    for (int i = 0; i < N - 1; i++)
        for (int j = 0; j < N - 1 - i; j++)
            if (balloon[j] > balloon[j + 1]) { int temp = balloon[j]; balloon[j] = balloon[j + 1]; balloon[j + 1] = temp; }
    // 学生身高升序排序（冒泡排序）
    for (int i = 0; i < M - 1; i++)
        for (int j = 0; j < M - 1 - i; j++)
            if (student[j] > student[j + 1]) { int temp = student[j]; student[j] = student[j + 1]; student[j + 1] = temp; }
    int total = 0;  // 摘到的气球总数
    // 从高到矮处理每位学生：让他优先摘能摘到的最高的气球，最多摘2个
    for (int i = M - 1; i >= 0; i--) {
        int cnt = 0;  // 这位学生已经摘到的气球数
        for (int j = N - 1; j >= 0 && cnt < 2; j--) {
            if (!taken[j] && balloon[j] <= student[i]) {
                taken[j] = true;
                cnt++;
                total++;
            }
        }
    }
    cout << total << endl;
    return 0;
}

复杂度分析

把 N 个气球和 M 位同学排序，冒泡排序的时间是 O(N²+M²)，因为 N、M 都不超过 100，完全够快。摘气球时，最坏情况下每位同学都要扫一遍所有气球，时间是 O(N×M)。空间上只用了几个长度为 105 左右的数组，是 O(N+M)。整体时间大概百万次运算以内，非常轻松。