解题思路

成人票 8 元、儿童票 3 元，一共花了 40 元，成人和儿童都有。求可能的成人、儿童人数组合。

思路：枚举成人人数。

1. 成人 c 人，花了 c×8 元
2. 剩下的 40 - c×8 元买儿童票，要能被 3 整除
3. 成人至少 1 人，且要留钱给儿童，所以成人最多 (40-3)÷8 人
4. 能整除就输出这一组

为什么成人从少到多、儿童从多到少自动满足？ 成人 c 从小到大枚举，花在成人上的钱越来越多，儿童人数自然越来越少。

举例：c=1，成人花 8 元，剩 32 元，32÷3 不整除；c=2，剩 24 元，24÷3=8 个儿童，输出 2 8……

参考代码

#include <iostream>
using namespace std;

int main() {
    for (int c = 1; c <= (40 - 3) / 8; c++) {  // 成人人数
        if ((40 - c * 8) % 3 == 0) {  // 剩余能整除儿童票
            cout << c << " " << (40 - c * 8) / 3 << endl;
        }
    }
    return 0;
}

复杂度分析

• 时间复杂度：O(1)，枚举到最多 4 个成人
• 空间复杂度：O(1)