P10056 Water题解

Leo2011的博客 / 2024-01-15 / 原文

~~唯一一道赛场 AC 的题~~，发篇题解记录一下

思路：

“保证无论如何操作都不会溢出”——前 2 个点的特殊性质。

那么这种情况下，最佳方案自然就是全倒到 1 个杯子里。

那么如果会溢出呢？

倒了就溢出，那就别倒了呗（废话）。

所以总结一下，我们的操作就是如果全倒到 1 个杯子里不超容积，那就全倒，否则，就是不超容积时能倒的最大次数。

举个例子：

样例 1， $2 \times 2 = 4 < 5$，因此全倒到某个杯子里，最大为 $4$。

样例 2， $5 \times 2 = 10 < 11, 5 \times 3 = 15 > 11$，因此最大是 $2$ 杯容量 $10$。

Code：

/*Code by Leo2011*/
#include <bits/stdc++.h>

#define INF 0x3f3f3f3f
#define EPS 1e-8
#define FOR(i, l, r) for (int(i) = (l); (i) <= (r); ++(i))
#define log printf
#define IOS                      \
	ios::sync_with_stdio(false); \
	cin.tie(nullptr);            \
	cout.tie(nullptr);

using namespace std;

typedef long long ll;

ll a, b, n, ans;  // 1e18，不开long long见祖宗

template <typename T>

inline T read() {
	T sum = 0, fl = 1;
	char ch = getchar();
	for (; !isdigit(ch); ch = getchar())
		if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = sum * 10 + ch - '0';
	return sum * fl;
}

template <typename T>

inline void write(T x) {
	static T sta[35];
	int top = 0;
	do {
		sta[top++] = x % 10, x /= 10;
	} while (x);
	while (top) putchar(sta[--top] + 48);
}

int main() {
	a = read<ll>(), b = read<ll>(), n = read<ll>();
	while (1) {  // 无限次尝试
		if ((ans + b > a) || (!n)) break;  // 倒不了了或者都倒完了就退出
		n--;  // 倒掉一个杯子，这个杯子就没用了
		ans += b;  // 增加这个杯子的容量
	}
	write(ans);
	return 0;
}