C#算法之大牛生小牛的问题高效解决方法

问题描述

题目来源于 LeetCode，现在有一只大牛和一只小牛，它们的初始体重分别为 $x$ 和 $y$，每年它们的体重都会增加固定的比例（比例为 $p$），求当小牛的体重超过大牛的体重时，需要多少年。

解题思路

考虑使用循环解决。

每年大牛的体重增加 $p$%，小牛的体重增加 $2p$%，那么循环条件可以设为小牛体重小于等于大牛体重，即：

while(y <= x) 
{
    x += x * p / 100;
    y += y * 2 * p / 100;
    year++;
}

细节要点：

• 要开一个计数器 year 来记录年份；
• 在循环前需初始化 year 为 0，否则会计算错误。

代码实现

public class Solution {
    public int GetYears(int x, int y, int p) {
        int year = 0;

        while(y <= x) 
        {
            x += x * p / 100;
            y += y * 2 * p / 100;
            year++;
        }

        return year;
    }
}

测试样例

下面给出两个示例说明。

示例1

输入：

x = 100, y = 50, p = 10%

输出：

6

解释：

当小牛体重达到 $146.41$ 公斤，大牛体重为 $142.74$ 公斤时，小牛的体重将会大于大牛的体重，此时已经过了 $6$ 年。

示例2

输入：

x = 100, y = 50, p = 2%

输出：

19

解释：

当小牛体重达到 $98.19$ 公斤，大牛体重为 $98.04$ 公斤时，小牛的体重将会大于大牛的体重，此时已经过了 $19$ 年。