1049.百钱百鸡 - 帖子

经典枚举题

枚举的大概流程：在不考虑题目要求的限制下，考虑两个极端情况(一般都是最小和最大的情况)，先买公鸡，再去买母鸡，最后买小鸡，这个过程必定有很多不合理的方案，只需要交给if去验证就行，验证通过就是答案

法1：究极无脑暴力枚举

1）枚举过程

根据题意，三种鸡的总数必须买到100只。不用思考，那么每只鸡可选的范围就是0~100只

所以直接暴力三层循环：

// 举例买公鸡的情况
for(int i=0;i<=100;i++){
    // 举例买母鸡的情况
    for(int j=0;j<=100;j++){
        // 举例买小鸡的情况
        for(int k=0;k<=100;k++){
            // 验证
        }
    }
}

2）验证过程

经过三层循环的枚举，公鸡有i只、母鸡有j只、小鸡有k只：

PS:公鸡5元一只，母鸡3元一只，小鸡1元三只

公鸡的数量 + 母鸡的数量 + 小鸡的数量 = 100

买公鸡的钱 + 买母鸡的钱 + 买小鸡的钱 = 100

隐藏条件：小鸡的只数必须是三的倍数（钱不能为小数）

根据以上条件进行验证：

// 钱数验证、只数验证、小鸡的特殊判断
if(i*5+j*3+k/3==100 && i+j+k==100 && k%3==0){
    // 输出
}

3）输出：

先输出小鸡、再输出母鸡、最后输出公鸡，并且答案不止一组，所以每种情况后要换行

cout<<k<<" "<<j<<" "<<i<<endl;

完整代码：

#include<iostream>
using namespace std;
int main(){
// 举例买公鸡的情况
	for(int i=0;i<=100;i++){
// 举例买母鸡的情况
		for(int j=0;j<=100;j++){
// 举例买小鸡的情况
			for(int k=0;k<=100;k++){
// 从钱数和鸡的只数判断方案是否合理
				if(i5+j3+k/3==100 && i+j+k==100 && k%3==0){
cout<<k<<" "<<j<<" "<<i<<endl;
}
}
}
}
return 0;
}

4）稍微动脑

100元的情况下，公鸡最多20只，范围就是0~20；母鸡最多33只，范围就是0~33；小鸡最多99只(只数最多100)，范围就是0~99

// 举例买公鸡的情况
for(int i=0;i<=20;i++){
    // 举例买母鸡的情况
    for(int j=0;j<=33;j++){
        // 举例买小鸡的情况
        for(int k=0;k<=99;k++){
            // 验证
        }
    }
}

法2：枚举的优化(减少循环层数)

根据题目鸡的总数量为100可以得出，当公鸡有i只，母鸡有j只时，小鸡的数量不用枚举，可以直接通过计算得出，因此可以减少循环层数：

小鸡的数量k = 100 - 公鸡数量i - 母鸡数量j

那么也不需要再验证鸡的总数为100

// 举例买公鸡的情况
for(int i=0;i<=20;i++){
    // 举例买母鸡的情况
    for(int j=0;j<=33;j++){
        // 举例买小鸡的情况
        int k = 100 - i - j;
        // 验证
        if(i*5+j*3+k/3==100 && k%3==0){
            cout<<k<<" "<<j<<" "<<i<<endl;
        }
    }
}