水壶问题 C++

假设我们有两个容量为 x 升和 y 升的水壶。供应给我们的是无限量的水。现在，我们需要确定是否が可能，仅使用这两个水壶量出 z 升水。如果能够量出 z 升的水，那么到最后，其中一只水壶或两只水壶中必定装有 z 升水。

我们可以执行以下几个操作 -

  • 将其中一只水壶灌满水。

  • 清空其中一只水壶。

  • 将一只水壶中的水倒入另一只水壶，直到另一只水壶被完全灌满水或第一只水壶被清空。

因此，如果 x = 2 且 y = 5，以及 z = 4，那么它将返回 true。

为了解决此问题，我们将按照以下步骤进行 -

  • if x + y < z，则返回 false

  • if x = z 或者 y = z，或者 x + y = z，则返回 true

  • if z 整除 x 和 y 的最大公约数，则返回 true，否则返回 false

示例 (C++)

为了帮助我们更好地理解，让我们看下面的实现 -

 在线演示

#include <bits/stdc++.h&g;
using namespace std;
class Solution {
   public:
   bool canMeasureWater(int x, int y, int z) {
      if(x + y < z) return false;
      if(x == z || y == z || x + y == z) return true;
      return z % __gcd(x, y) == 0;
   }
};
main(){
   Solution ob;
   cout << (ob.canMeasureWater(3,5,4));
}

输入

3
5
4

输出

1

更新日期： 02-5-2020

2 千+ 次浏览

开启你的职业生涯

完成课程，获得认证

开始
广告