【codeforces】526C Om Nom and Candies 题解

题目大意

有两类糖果，重量与美味值分别为$w_1,h_1,w_2,h_2$。
求: 拿取重量不超过$C$的糖果，美味值最大为多少？
$(1\le w_1,h_1,w_2,h_2,C\le 10^9)$

原题链接

思路

由于数据量较大，所以无法$dp$,但考虑到只有两种糖果，可以考虑贪心 （乱搞） 做法。

首先我们肯定是多带性价比最高的糖果，然后剩下的空间带另一种。
但这样做有一种弊端，就是存在某种大小剩余空间，恰好可以装很多性价比低的，而性价比高的会少放一个，导致这时候放性价比低的会使得结果更优（比如题目的样例）。

所以我们应该找到一种绝对更优的贪心策略，哪怕它只是局部的，我们假设$\frac{h_1}{w_1}>\frac{h_2}{w_2}$:
那么如果我们买到了$w_1$个$2$号糖果，它提供的美味值是$w_1?h_2$,那么我们把它换成$w_2$个$1$号糖果，显然会更优，因为相同的重量，美味值更大了($w_2?h_1$)，也就是说，我们肯定不会买超过$w_1$个$2$号糖果。

所以另一种思路就是，枚举购买多少糖果，而我们需要尽量减少枚举次数，我们的操作都围绕着这个展开，包括之前的贪心策略，由此可以得到下面的做法:

1. 假如一种糖果的重量超过了$\sqrt{C}$，那么就太好了，我们甚至可以不用贪心，直接枚举买多少个这种糖果就好了。
2. 如果都不是，那么我们就按照贪心做法，因为我们不会买超过$w_1$个$2$号糖果，所以我们枚举买多少个$2$号糖果即可。

代码

#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;long long c, h1, h2, w1, w2;int main()
{
    cin >> c >> h1 >> h2 >> w1 >> w2;if(w1 > w2) swap(h1, h2), swap(w1, w2);if(w2 > sqrt(c)){
    long long ans = 0;for(int i = 0; i * w2 <= c; i++) ans = max(ans, i * h2 + (c - i * w2) / w1 * h1);cout << ans;}else{
    long long ans = 0;if(h1 * w2 < w1 * h2) swap(h1, h2), swap(w1, w2);for(int i = 0; i <= w1; i++) ans = max(ans, i * h2 + (c - i * w2) / w1 * h1);cout << ans;}return 0;
}