题解 | #Water#_牛客博客

M题

由裴蜀定理容易判断是否有解。接下来考虑如何算最小操作次数

设 $C = x A + y B$ ， $A \leq B$

那么 $(x, y)$ 只会出现以下三种情况（ $0$ 归为 $+$ 或 $-$ 都行）

$\bullet$ $(+, +)$ ，此时最小操作次数为 $2 (x + y)$ 。

这种情况没有互相倒水操作。

$\bullet$ $(+, -)$ ，此时最小操作次数为 $2 (x - y) - 1$ 。

这种情况是A装满水往B杯倒，最优策略是B装满了B才往外倒，如果把B装满后，A中还有剩的，此时直接喝掉A中的水。

$\bullet$ $(-, +)$ ，此时最小操作次数为 $2 (y - x) - 1$ 。

这种情况是B装满水往A杯倒，最优策略是A装满了A才往外倒，如果B杯剩下的水不足以倒满A杯，那就不需要往A倒，此时直接喝下。

最终答案为三种情况中取最小值。这三种情况都要使x的绝对值尽可能小,这样能使答案最小。

C++ Code

#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const LL INF = 0x3f3f3f3f3f3f3f3f;
LL exgcd(LL a, LL b, LL&x, LL&y)
{
	LL ret, tmp;
	if (!b) {
		x = 1; y = 0;
		return a;
	}
	ret = exgcd(b, a % b, x, y);
	tmp = x;
	x = y;
	y = tmp - a / b * y;
	return ret;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int T;
	cin >> T;
	while (T--) {
		LL a, b, c, ans = INF;
		cin >> a >> b >> c;
		if (a > b) swap(a, b);
		LL x = 0, y = 0;
		LL Gcd = exgcd(a, b, x, y);
		if (c % Gcd != 0) cout << "-1\n";
		else {
			LL k = c / Gcd;
			x *= k; y *= k;
			LL p = b / Gcd, q = a / Gcd, t;
			//x转为绝对值最小
			t = x / p; x -= p*t; y += q*t;
			if (x >= 0 && y >= 0) ans = min(ans, 2LL*(x+y));
			else ans = min(ans, 2LL*abs(x-y)-1);
			//x转为另一个符号
			if (x*p >= 0) x -= p, y += q;
			else x += p, y -= q;
			if (x >= 0 && y >= 0) ans = min(ans, 2LL*(x+y));
			else ans = min(ans, 2LL*abs(x-y)-1);
			cout << ans << "\n";
		}
	}
	return 0;
}