B3754 鸡兔同笼 题解

· · 题解

B3754 鸡兔同笼 题解

（这题竟然一个题解都没有？

题意

三种动物，一种 1 头 2 脚（坤鸡），一种 1 头 3 脚（3 脚猫），一种 1 头 4 脚（兔）。

求一头 4 脚的最 多/少 有几只？

题解

注意到数据范围 x \le 10^9 所以肯定暴力枚举过不了QAQ

考虑数学方法。

样例：

12345 40000

假设这 12345 个头 都是 3 脚猫 的，那么就会有 12345 \times 3 = 37035 条腿。

但是，题目告诉我们 一共有 40000 条腿……

如果我们用 一只兔子替换一只 3 脚猫，那么总共产生的腿数就会 多 4 - 3 = 1 条：

\begin{aligned} 12345 - 1 &= 12344 （这是 3脚猫的只数） \\ 12344 \times 3 + 1 \times 4 &= 37036 （正好多1） \end{aligned}

既然这样，我们 少了多少腿，就用 几只兔子替换 3 脚猫，就可以让腿数达到 40000。

\begin{aligned} 40000 - 37035 &= 2965 （全部是3脚猫少了的腿数）\\ 12345 - 2965 &= 9380 （替换一部分为兔子后的腿数） \\ 9380 \times 3 + 2965 \times 4 &= 40000 （刚刚好是40000） \end{aligned}

所以，求最少几只兔子的公式就是

y - 3 x （x是头数，y是腿数）

样例：

6 21

跟刚才一样假设，由于是求 最多 有多少只兔子，所以我们假设这全都是兔子，一共 4 \times 6 = 24 条腿。这比要求的腿数多了 24 - 21 = 3 条。

题目中的坤鸡有2条腿，用1只坤鸡替换兔子会少 4 - 2 = 2 条腿。

3 \div 2 = 1\text{ 余 }1

注意有余数，这种情况就要一只 3 脚猫 替换 1 只兔子，会少 4 - 3 = 1 条腿，刚好将余数去掉。所以一共要用 \lceil \frac{3}{2} \rceil 只 非兔子 的动物替换兔子。

公式：

x - \lceil \frac{4x - y}{2} \rceil （总只数减去非兔子的只数）

代码

class Solution {
    int ans1, ans2;
    void solve(int x, int y) {
        int t = 4 * x - y; // 分子提前算出
        ans1 = max(0, y - 3 * x);  // 最少只数
        ans2 = max(0, x - (t>>1) + (t&1)); // 最多只数
    }
    // 输入输出就不放了 :D
}

(看在蒟蒻这么辛苦地打公式，就点个赞再走吧 qwq