【例4.14】百钱买百鸡

GitHub跳转原题关系图返回列表

通过两层循环枚举鸡翁和鸡母的数量,根据百鸡计算鸡雏数量,并判断钱数是否等于一百。

OJ: roj

题目 ID: 5030

难度:入门

标签:暴力枚举

创建: 2026-10-08 19:48

更新: 2026-10-08 19:48

形式化题目

已知鸡翁每只 55 钱,鸡母每只 33 钱,鸡雏 33 只 11 钱。 现有 100100 钱,要买 100100 只鸡。 求鸡翁(roosterrooster)、鸡母(henhen)、鸡雏(chickchick)各买多少只? 要求按照鸡翁数量从小到大输出所有可行解。

即求满足以下条件的所有非负整数解 (rooster,hen,chick)(rooster, hen, chick):

  1. rooster+hen+chick=100rooster + hen + chick = 100
  2. 5×rooster+3×hen+chick3=1005 \times rooster + 3 \times hen + \frac{chick}{3} = 100
  3. chick mod 3=0chick \bmod 3 = 0

输出格式:每行输出一组解的 rooster,hen,chickrooster, hen, chick,用空格分隔,末尾带有单个换行,按 roosterrooster 升序排列。

正解

思路

这是一道经典的枚举题目。 朴素的做法是写三重循环,分别枚举 rooster,hen,chickrooster, hen, chick,但这样时间复杂度是 O(1003)O(100^3),不够优。

优化思路:

  1. 由于总数为 100100,只要确定了 roosterrooster 和 henhen,chickchick 的值就固定为 100−rooster−hen100 - rooster - hen。这样可以省去 chickchick 的枚举,将复杂度降为两重循环。
  2. 进一步缩小枚举范围:
    • 鸡翁 55 钱一只,最多买 100/5=20100 / 5 = 20 只,因此循环条件为 rooster×5≤100rooster \times 5 \le 100。
    • 鸡母 33 钱一只,最多买 100/3=33100 / 3 = 33 只,因此循环条件为 hen×3≤100hen \times 3 \le 100。
  3. 对每个确定的 roosterrooster 和 henhen,求出 chick=100−rooster−henchick = 100 - rooster - hen。判断是否满足:
    • chick≥0chick \ge 0
    • chickchick 是 33 的倍数(因为鸡雏是按 33 只一组卖的)
    • 5×rooster+3×hen+chick/3=1005 \times rooster + 3 \times hen + chick / 3 = 100 如果全满足,则找到了一组解。题目要求按依次由小到大输出,我们的外层循环正是以 roosterrooster 从小到大枚举的,所以天然给出了升序输出。

代码

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 19:45
# update_at: 2026-10-08 19:45

TOTAL = 100            # 百钱买百鸡:鸡共 100 只、钱共 100 文
ROOSTER_PRICE = 5      # 鸡翁一只值钱 5
HEN_PRICE = 3          # 鸡母一只值钱 3
CHICK_PER_COIN = 3     # 鸡雏 3 只值钱 1,所以鸡雏数必须是 3 的倍数


def solve() -> None:
    """枚举鸡翁、鸡母并推出鸡雏,校验钱数后按鸡翁升序输出全部解。"""
    for rooster in range(TOTAL // ROOSTER_PRICE + 1):
        for hen in range(TOTAL // HEN_PRICE + 1):
            chick = TOTAL - rooster - hen
            if chick < 0 or chick % CHICK_PER_COIN:
                continue  # 鸡雏按 3 只一组卖,数量不是 3 的倍数时钱数无意义
            cost = rooster * ROOSTER_PRICE + hen * HEN_PRICE + chick // CHICK_PER_COIN
            if cost == TOTAL:
                print(rooster, hen, chick)


if __name__ == "__main__":
    solve()
cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-08 19:45
 * update_at: 2026-10-08 19:45
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll TOTAL = 100;        // 百钱买百鸡:鸡共 100 只、钱共 100 文
const ll ROOSTER_PRICE = 5;  // 鸡翁一只值钱 5
const ll HEN_PRICE = 3;      // 鸡母一只值钱 3
const ll CHICK_PER_COIN = 3; // 鸡雏 3 只值钱 1,所以鸡雏数必须是 3 的倍数

// 枚举鸡翁数、鸡母数,由「百鸡」推出鸡雏数,再校验「百钱」。
// 鸡翁从小到大枚举,输出天然按鸡翁升序,符合题面「依次由小到大」。
void solve() {
    for (ll rooster = 0; rooster * ROOSTER_PRICE <= TOTAL; rooster++) {
        for (ll hen = 0; hen * HEN_PRICE <= TOTAL; hen++) {
            ll chick = TOTAL - rooster - hen;
            // 鸡雏按 3 只一组卖,不能整除就没有对应钱数,直接跳过
            if (chick < 0 || chick % CHICK_PER_COIN != 0) {
                continue;
            }
            ll cost = rooster * ROOSTER_PRICE + hen * HEN_PRICE + chick / CHICK_PER_COIN;
            if (cost == TOTAL) {
                cout << rooster << " " << hen << " " << chick << "\n";
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();

    return 0;
}

复杂度

  • 时间复杂度:O(N×M)O(N \times M),其中 N=20,M=33N = 20, M = 33。外层循环执行 2121 次,内层循环执行 3434 次,总共约进行 700700 次判断,复杂度为常数级别 O(1)O(1),非常小。
  • 空间复杂度:O(1)O(1),只需常数级别的变量用于循环和计算。

总结

经典的一道利用等式约束减少循环层数的枚举题。 关键点及容易踩坑的地方如下:

  1. 隐藏条件与等价方程:本题等价于解三元一次方程组:
    rooster+hen+chick=100rooster + hen + chick = 100
    5×rooster+3×hen+chick3=1005 \times rooster + 3 \times hen + \frac{chick}{3} = 100
    将第一个式子的 chickchick 代入第二个式子,可以消元得到:
    7×rooster+4×hen=1007 \times rooster + 4 \times hen = 100
    由此可得 roosterrooster 必须是 4 的倍数(因为 4×hen4 \times hen 和 100100 都是 4 的倍数)。所以解的 roosterrooster 只能是 0,4,8,12,…0, 4, 8, 12, \dots。这也解释了为何最终只有这 4 组解(16×7>10016 \times 7 > 100 已经被排除)。
  2. 截断除法陷阱:鸡雏的价值是 13\frac{1}{3} 钱一只,说明鸡雏的数量 chickchick 必须是 33 的倍数。必须加上 chick % 3 == 0 的判断。如果不用这个判断,而是直接算整数除法 chick / 3 或向下取整 chick // 3,在 C++ 和 Python 中会发生截断,从而把本来不成立的解(花费变少)错误地判定为等于 100100。
  3. 输出顺序与格式:题目要求依次由小到大输出。通过将 roosterrooster 放在外层循环从小到大枚举,输出天然就是按 roosterrooster 升序的。另外,每行输出三个数并用空格隔开,末尾单个换行,且不要带有多余空行。