365. Water and Jug Problem

今天的题目是365. Water and Jug Problem

我们可以执行的操作有三种:

  • 给一个杯子装满
  • 倒掉一个杯子中的所有水
  • 将一个杯子中的水转移到另一个杯子中直到没水或者另一个杯子装满

三种操作会分别让两个杯子总水量产生三种:

  • 增加xy
  • 减少xy
  • 总量不变

上面的说法是没有考虑向一个未空的杯子中加水或者是从一个未空的杯子中加水的情况,因为这样的操作显然是没有意义的。

因此杯子中的总水量可以用ax+by表示,其中ab都是整数。此时问题转换为是否存在ab使得ax+by=z。根据裴蜀定理,我们可以用z % gcd(x,y)来判断。

代码如下:

1
2
3
4
5
6
7
8
9
10
int gcd(int x,int y) {
return x % y == 0 ? y : gcd(x, x % y);
}
bool canMeasureWater(int x, int y, int z) {
if (x == 0 && y == 0) return z == 0;
if (x + y < z) return false;
if (x > y) swap(x, y); // y >= x
int d = x ? gcd(y, x) : y;
return (z % d == 0);
}