【codeforces】526C Om Nom and Candies 题解

有两类糖果，重量与美味值分别为 w 1 , h 1 , w 2 , h 2 w_1, h_1, w_2, h_2 w1​,h1​,w2​,h2​。
求: 拿取重量不超过 C C C的糖果，美味值最大为多少？
( 1 ≤ w 1 , h 1 , w 2 , h 2 , C ≤ 1 0 9 ) (1 le w_1, h_1, w_2, h_2, C le 10^9) (1≤w1​,h1​,w2​,h2​,C≤109)

原题链接

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

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

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

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

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

#include 
#include 
#include 
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;
}