【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 \cdot h_2$，那么我们把它换成 $w_2$ 个 1 号糖果，显然会更优，因为相同的重量，美味值更大了（$w_2 \cdot h_1$），也就是说，我们肯定不会买超过 $w_1$ 个 2 号糖果。

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

1. 假如一种糖果的重量超过了 $\sqrt{C}$，那么我们甚至可以不用贪心，直接枚举买多少个这种糖果就好了（枚举次数 $\le \sqrt{C}$）。
2. 如果都不是，那么我们就按照贪心做法，因为我们不会买超过 $w_1$ 个 2 号糖果（$w_1 \le \sqrt{C}$），所以直接枚举买多少个 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;
}