阿里编程测验题目交流

题目描述：

1. 猎人把一对兔子婴儿(一公一母称为一对)放到一个荒岛上，两年之后，它们生下一对小兔，之后开始每年都会生下一对小兔。生下的小兔又会以同样的方式继续繁殖。
2. 兔子的寿命都是x(x>=3)年，并且生命的最后一年不繁殖。
3. 如果岛上的兔子多于10对，那么猎人会每年在兔子们完成繁殖或者仙逝之后，从岛上带走两对最老的兔子。
   请问y年(y>=3)后荒岛上所有的兔子加起来多少岁?
   输入: 从命令行输入两行整数，第一行是x，第二行是y
   输出: y年后荒岛上所有的兔子岁数的总和

我的思路：维护一个队列or链表，每年新加入的兔子从队尾加入，死掉的兔子总是从队首去除。队列长度<=x。时间复杂度O(x*y)，空间复杂度O(x)。
我的代码：

#include <iostream>
#include <list>
using namespace std;
struct Rabbit
{
    long long age;
    long long num;
    Rabbit(long long age, long long num):age(age), num(num){}
};
int main()
{
    long long x, y;
    while(cin>>x>>y)
    {
        list<Rabbit> l;
        l.push_back(Rabbit(0, 1));
        long long sumRabbitNum = 1;
        for(int year = 1; year <= y; ++year)
        {
            list<Rabbit>::iterator it;
            for(it = l.begin(); it != l.end(); it++)
            {
                it->age++;
            }
            it = l.begin();
            while(it != l.end())
            {
                if(it->age >= x)
                {
                    sumRabbitNum -= it->num;
                    l.pop_front();
                    it = l.begin();
                }
                else break;
            }
            long long newRabbitCnt = 0;
            for(it = l.begin(); it != l.end(); it++)
            {
                if(it->age >= 2) newRabbitCnt += it->num;
            }
            if(newRabbitCnt) l.push_back(Rabbit(0, newRabbitCnt));
            sumRabbitNum += newRabbitCnt;
            if(sumRabbitNum > 10)
            {
                sumRabbitNum -= 2;
                list<Rabbit>::iterator it = l.begin();
                if(it->num > 2) it->num -= 2;
                else if(it->num == 2) l.pop_front();
                else
                {
                    l.pop_front();
                    it = l.begin();
                    if(it->num > 1) it->num--;
                    else
                    {
                        l.pop_front();
                    }
                }
            }
        }
        long long sumRabbitAge = 0;
        for(list<Rabbit>::iterator it = l.begin(); it != l.end(); it++)
        {
            sumRabbitAge += it->age * it->num;
        }
        sumRabbitAge <<= 1;
        cout<<sumRabbitAge<<endl;
    }
    return 0;
}

时间复杂度可以优化到O(y)。
优化思路：
1.把Rabbit中的age字段改为出生年份，这样就不用遍历队列去更新age了；
2.求年龄>=2的兔子数，可以用总的兔子数减去队尾一个节点的兔子数。
优化后的代码：

#include <iostream>
#include <list>
using namespace std;
struct Rabbit
{
    long long birth;
    long long num;
    Rabbit(long long birth, long long num) : birth(birth), num(num){}
};
int main()
{
    int x, y;
    while(cin>>x>>y)
    {
        list<Rabbit> q;
        q.push_back(Rabbit(0, 1));
        long long sumRabbit = 1;
        for(int i = 1; i <= y; ++i)
        {
            auto it = q.begin();
            if(it != q.end() && i - it->birth >= x)
            {
                sumRabbit -= it->num;
                q.pop_front();
            }
            long long sumNewRabbit = sumRabbit;
            auto rit = q.rbegin();
            if(rit != q.rend() && i-rit->birth < 2) sumNewRabbit -= rit->num;
            if(sumNewRabbit > 0) q.push_back(Rabbit(i, sumNewRabbit));
            sumRabbit += sumNewRabbit;
            if(sumRabbit > 10)
            {
                sumRabbit -= 2;
                it = q.begin();
                if(it->num > 2) it->num -= 2;
                else if(it->num == 2) q.pop_front();
                else
                {
                    q.pop_front();
                    it = q.begin();
                    if(it->num > 1) it->num--;
                    else q.pop_front();
                }
            }
        }
        long long sumAge = 0;
        for(auto it = q.begin(); it != q.end(); it++) sumAge += (y - it->birth) * it->num;
        sumAge <<= 1;
        cout<<sumAge<<endl;
    }
    return 0;
}