cf526C

题目大意

有两类糖果，重量与美味值分别为\(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;
}

• 本文作者： 水蓝络合物
• 本文链接： https://miku39393939.github.io/2022/03/27/cf526C/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！