瞎看脉脉的时候看到有人吐槽面试了AB两个瓶子倒水问题，然后回顾了下扩展欧几里得公式。搜着的时候看了这个算法题。还是很有意思的。
两个方法：1. 纯bfs搜；2. 数论解法
下面的这个链接用数论方法过程论证了一下。但是在最后的一段说明我觉得是有问题的。虽然结果是对的。
扩展欧几里得解法
所以|x+|y|的最小值为(c+d)/2，通过x和y的通解形式显然可以看出x和y一正一负，不妨设x<0，那么就是往第一个小瓶子倒进x次，第二个小瓶子倒出y次，但是由于瓶子容积有限，所以倒进倒出操作都是通过大瓶子来解决的，一次倒进操作后为了继续使用小瓶子还要将小瓶子中可乐倒回大瓶子中，倒出操作同理，所以总操作次数是(c+d)/2*2=c+d，但是注意最后剩下的(a+b)/2体积的可乐一定是放在两个小瓶子中较大的那个中，而不是再倒回到大瓶子中，所以操作数要减一，答案就是c+d-1
分析到(c+d)/2*2=c+d都是对的。之后的解释应该是：假设N<M,最后可乐可能会在3杯或者2杯了，但是无论如何一定是在S或者M里面有1/2的量。N小的倒入的，M大的是倒出的。此时在最后一次，小的倒入之后，是不需要倒出的，因为此时，如果再倒给M杯，M杯达到了1/2，那说明此时N+M已经是1/2，所以不需要再倒，所以是c+d-1。
举个例子：
S=10， N=3, M=7.
1: 7, 3, 0
2: 7, 0, 3
3: 4, 3, 3
4: 4, 0, 6
5: 1, 3, 6
6: 1, 2, 7 ---
7: 8, 2, 0 ---
8: 8, 0, 2
9: 5, 3, 2
1|2, 3|4, 5|8都是小杯子的进，然后对应出， 9就是进，不出了
6|7是大杯子的出，出的前提是有一个进。
这里5和8对应，应为经过了三步才把小杯子的进的3清空。中间穿插了大杯子的出-进的关系，出是7，进也就是装满操作6。
其他例子也是这么解释。
网友评论