2017阿里C++研發工程師-校招-筆試模擬 - acm1314－IT工程師數位筆記本

文章出處

題目描述：

獵人把一對兔子嬰兒(一公一母稱為一對)放到一個荒島上，兩年之后，它們生00下一對小兔，之后開始每年都會生下一對小兔。生下的小兔又會以同樣的方式繼續繁殖。

兔子的壽命都是x(x>=3)年，并且生命的最后一年不繁殖。

如果島上的兔子多于10對，那么獵人會每年在兔子們完成繁殖或者仙逝之后，從島上帶走兩對最老的兔子。
請問y年(y>=3)后荒島上所有的兔子加起來多少歲?(注意, 在條件3執行完之后)

輸入: 從命令行輸入兩行整數，第一行是x，第二行是y
輸出: y年后荒島上所有的兔子歲數的總和

樣例：

輸入：
3
3
輸出：
2

解題思路：

開一個數組， tu[j] 表示在第某年年末， j 歲大的兔子對數。然后每過一年 tu[j] = tu[j-1] (j >= 1), tu[0] 為新生的兔子對數。
手動模擬幾組數據

年份(年末)/兔子年齡， 為了簡單，先不考慮兔子年齡限制，不考慮超過十對時取走兩對年齡大的兔子。

           0        1        2        3        4        5        6      

1          0        1

2          1        0       1

3          1        1       0        1

4          2        1       1        0         1    

5          3        2        1       1        0         1 

6          5         3        2        1       1        0         1

然后假設兔子年齡限制為 5，并且超過十對時取走兩對年齡大的兔子。

年份(年末)/兔子年齡，假設 兔子年齡限制為 5， 并且超過十對時取走兩對年齡大的兔子。

           0        1        2        3        4        5        6      

1          0        1

2          1        0       1

3          1        1       0        1

4          2        1       1        0         1    

5          3        2        1       1        0        0

6          4        3        2        0       0        0         0 

7          5        4        3        0       0        0         0

吐槽：年末年初的問題好容易搞混啊，以及兔子生命最后一年的情況，需要靜下心慢慢分析，才能“蒙對”題意 -_- || 。

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <list>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <stdexcept>
#include <cstdio>
#include <cstdlib>
using namespace std;

int result(int x, int y)
{
    vector<int> tu(x+5, 0); 
    tu[1] = 1; 
    for(int i = 2; i <= y; i++)
    {
        int newTu = 0; 
        for(int j = x+1; j >=1; j--)
        {
            tu[j] = tu[j-1]; 
            if(j >= 2 && j <= x)
                newTu += tu[j]; 
        }
        tu[0] = newTu; 

        int lastY = 0; 
        int tot = 0; 
        for(int j = x; j >= 0; j--)
        {
            tot += tu[j]; 
            if(lastY == 0 && tu[j])
                lastY = j; 
        }
        if(tot > 10)
        {
            if(tu[lastY] >= 2)
                tu[lastY] -= 2; 
            else
            {
                tu[lastY] = 0; 
                for(int k = lastY-1; k >= 0; k--)
                    if(tu[k])
                    {
                        tu[k] -= 1; 
                        break; 
                    }
            }
        }
    }

    int ans = 0; 
    for(int i = 1; i <= x; i++)
        ans += tu[i] * i; 
   
    return ans*2; 
}

int main()
{
    int x, y; 
    cin >> x; 
    cin >> y; 
    int res = result(x, y); 
    cout << res << endl; 

    return 0; 
}