公鸡一个五块钱，母鸡一个三块钱，小鸡三个一块钱。 要用n块钱买n只鸡。 问公鸡、母鸡、小鸡各多少只？ 优化算法，要求算法时间复杂度为O(n) 写出优化Cpp算法,n由键盘输入

这个问题是一个经典的组合数学问题，也被称为“鸡兔同笼”问题的变种，可以用动态规划的思想解决。由于题目要求时间复杂度为 O(n)，我们可以遍历从0到n的所有金额，对于每个金额i，我们尝试找出所有可能的公鸡、母鸡和小鸡的数量组合，使得总花费等于i。

以下是使用 C++ 编写的优化算法：

#include <iostream>
using namespace std;

void buyChickens(int n) {
    for (int i = 0; i <= n; ++i) {
        int numCoins = n - i;
        if (numCoins % 5 == 0 && numCoins / 5 >= i) { // 公鸡的费用
            int roosters = i;
            int hens = (numCoins / 5) - i; // 母鸡的费用
            int chicks = numCoins / 3 - hens; // 小鸡的费用

            // 如果计算得到的小鸡数量大于0，则这个组合有效
            if (chicks > 0) {
                cout << "公鸡：" << roosters << " 只, 母鸡：" << hens << " 只, 小鸡：" << chicks << " 只" << endl;
            }
        }
    }
}

int main() {
    int n;
    cout << "请输入你想花的钱数：";
    cin >> n;
    buyChickens(n);
    return 0;
}

在这个算法中，我们首先检查剩余的钱是否可以全部通过公鸡购买，然后减去公鸡的数量后看剩下的钱能否通过母鸡和小鸡组合购买。如果能，则找到了一个有效的解。我们不断更新当前的公鸡和母鸡数量，并检查是否能构成整数个的小鸡，直到遍历完所有的可能性。