You are given two jugs with capacities jug1Capacity and jug2Capacity litres. There is an infinite amount of water supply available. Determine whether it is possible to measure exactly targetCapacity litres using these two jugs.

If yes, then you would need to determine how to achieve the target capacity. You may fill up any jug to its capacity, empty any jug, or pour water from one jug into another till it's full or the other jug is empty.

输入格式:

A triple (jug1Capacity, jug2Capacity, targetCapacity) representing the capacity of the two jugs, and the required target capacity.

输出格式:

A boolean value representing whether it is possible to fill the jugs such that one of them contains exactly targetCapacity litres of water.

示例:

输入样例:

jug1Capacity = 3, jug2Capacity = 5, targetCapacity = 4

输出样例:

true

说明: This problem is inspired from "Die Hard".

输入样例:

jug1Capacity = 2, jug2Capacity = 6, targetCapacity = 5

输出样例:

false

输入样例:

jug1Capacity = 1, jug2Capacity = 2, targetCapacity = 3

输出样例:

true

数据范围:

1 <= jug1Capacity, jug2Capacity, targetCapacity <= 106

题目分析

著名的 "Die Hard" 问题。

过程很像 更相减损术

结论:

$$ a \times \text{jug1Capacity} + b \times \text{jug2Capacity} = \text{canGetedCapacity} $$

由 贝祖定理:

$$ ax + by = m $$

This equation has integer solutions if and only if m is a multiple of the greatest common divisor (gcd) of a and b. When the Bézout's Identity has solutions, there are infinitely many integer solutions. Each pair of solutions (x, y) are called Bézout's numbers, which can be obtained using the Extended Euclidean Algorithm.

代码实现

class Solution {
public:
    bool canMeasureWater(int g1, int g2, int tar) {
        return g1 + g2 >= tar && tar
    }
};
分类: Math

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status