有红蓝两种糖果,红色糖果每颗重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;
}