题目描述

一个笼子里面关了鸡和兔子（鸡有2只脚，兔子有4只脚，没有例外）。已经知道了笼子里面脚的总数a，问笼子里面至少有多少只动物，至多有多少只动物

输入

第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，每行一个正整数a (a < 32768)

输出

输出包含n行，每行对应一个输入,包含两个正整数，第一个是最少的动物数，第二个是最多的动物数，两个正整数用一个空格分开
如果没有满足要求的答案，则输出两个0。

样例输入

2
3
20

样例输出

0 0
5 10

这道题不涉及算法，首先想到的就是暴力枚举

#include<iostream>
using namespace std;
int main()
{
    int n,m;
    cin>>n;
    while(n--){
        cin>>m;
        int min=16384,max=0;//记录最少有多少动物，最多有多少动物
        for(int i=0;i<=m/2;++i){
            for(int j=0;j<=m/4;++j){
                if(i*2+j*4==m){
                    if(i+j<min)
                        min=i+j;
                    if(i+j>max)
                        max=i+j; 
                }
            }
        }
        if(min==16384&&max==0){
            max=min=0;
        }
        cout<<min<<" "<<max<<endl;
    }
    return 0;
 } 

但是超时！！！…

通过观察发现，其实当输入的是奇数时，肯定没有满足的情况，因为兔子四只脚，鸡两只脚，一个数乘4加上一个数乘2肯定是个偶数。所以要先通过if判断排除掉这种情况。

其次，当脚数为定值，鸡的数量确定时，那么兔子的数量也就知道了，这时就不用再枚举兔子的数量了。会节省很多时间

#include<iostream>
using namespace std;
int main()
{
    int n,m;
    cin>>n;
    while(n--){
        cin>>m;
        int min=16384,max=0;//记录最多有多少动物，最少有多少动物 
        if(m%2==0){
            for(int i=0;i<=m/2;++i){
                int j=(m-i*2)/4;
                if(i*2+j*4==m){
                    if(i+j<min)
                        min=i+j;
                    if(i+j>max)
                        max=i+j; 
                }
            }
        }
        else
            max=min=0;

        cout<<min<<" "<<max<<endl;
    }
    return 0;
} 

运行时间：3ms

再思考发现，要想求至少有多少只动物，即让兔子的数量要尽量多；要想求至多有多少只动物，即让鸡的数量要尽量多。

#include<iostream>
using namespace std;
int main()
{
    int n,m;
    cin>>n;
    while(n--){
        cin>>m;
        int min,max;
        if(m%2==0){
            for(int i=m/2;i>=0;i--){//此时要从最大的情况开始往下递减，这样省时！！！
                int j=m-i*2;
                if(j%4==0){
                    max=i+j/4;
                    break;//当兔子和鸡的总脚数为m时即找到最合适的情况了，跳出。
                }
            }
            for(int i=m/4;i>=0;i--){//此时要从最大的情况开始往下递减，这样省时！！！
                int j=m-i*4;
                if(j%2==0){
                    min=i+j/2;
                    break;////当兔子和鸡的总脚数为m时即找到最合适的情况了，跳出。
                }
            }
        }
        else
            max=min=0;

        cout<<min<<" "<<max<<endl;
    }
    return 0;
}

运行时间：2ms

最简代码：

即：在确定脚数为偶数的情况下，要想求最少有多少只动物，此时要让兔子最多，即N/4，但是偶数中有的偶数能整除4，有的不能，这就要分类讨论了，能整除的时候，最少有N/4只动物，不能整除的时候，最少有(N-2）/4+1只动物，不论什么时候，都是最多有N/2只鸡。算是分类讨论了

#include<iostream>
using namespace std;
int main()
{
    int n,m;
    cin>>n;
    while(n--){
        cin>>m;
        if(m%4==0)
            cout<<m/4<<" "<m/2<<endl;
        else if(m%2==0)
            cout<<(m-2)/4+1<<" "<<m/2<<endl;
        else
            cout<<"0"<<" "<<"0"<<endl;
    }
}

运行时间：3ms

这类题还是要先思考几番，肯定有简单思路！！！