51nod1548 欧姆诺姆和糖果

有红蓝两种糖果，红色糖果每颗重wr克，甜度为hr；蓝色糖果每颗重wb克，甜度为hb；有容量为C克的盒子，求能装下的最大甜度。
1<=C,hr,hb,wr,wb<=1E9

分析：记S=lcm(wr,wb)，那么对于S克容量，可以装S/wr颗蓝色糖果，也可以装S/wb颗红色糖果，甜度分别为S*hb/wr和S*hr/wb，应该选甜度更大的。因此在枚举时，红色糖果数只需要枚举[0,wb)，蓝色糖果数只需要枚举[0,wr)，应该选择范围更小的进行枚举。另外枚举范围也不会超过C/max(wr,wb)，最坏情况是wr和wb取sqrt(C)。

#include <bits/stdc++.h>
using i64 = long long;

void solve() {
	i64 C, hr, hb, wr, wb;
	std::cin >> C >> hr >> hb >> wr >> wb;

	i64 ans = 0;
	for (i64 i = 0; i * i <= C; i++) {
		if (i * wr <= C) {
			ans = std::max(ans, i * hr + (C - i * wr) / wb * hb);
		}
		if (i * wb <= C) {
			ans = std::max(ans, i * hb + (C - i * wb) / wr * hr);
		}
	}
	std::cout << ans << "\n";
}

int main() {
	std::cin.tie(0)->sync_with_stdio(0);
	int t = 1;
	while (t--) solve();
	return 0;
}