题解 | 游游的水果大礼包

解法：枚举（注意：这道题贪心是错的）

枚举解法分析

因为我们要求的是最终能组成的最大的价值总和，如果我们假设最终的答案有x和一号礼包，y个二号礼包，那么最终的答案其实就是求 x*a + y*b 的最大值。

直接使用数学方法求不出来x和y的取值。那么我们就可以枚举一下x和y。其实就是枚举一个值，然后取出另一个值，取其中的 x*a + y*b 的最大值。

假如我们这里枚举的是x，然后求y的值。

1. 首先，我们需要知道x的取值范围，才能来枚举，最小值肯定是0，那么最大值呢？x是一号礼包的个数，而一个礼包需要苹果2个，需要桃子1个，这里有n个苹果，m个桃子，如果要让一号礼包取到不能再取了，那么x的最大取值就应该是 n/2 的 m 之间的最小值，即 min(n/2, m) 。
2. 求二号礼包的个数 y ，需要根据一号礼包的个数来计算。一号礼包有x个，那么二号礼包就是在 n - x*2 个苹果和 m - x 个桃子中组合了。由于一个二号礼包需要1个苹果和2个桃子，那么二号礼包最多就能取到当前的桃子数目除以2和当前苹果的数目之间的最小值了，即min(n-2*x, (m-x)/2)。

总结

所以，我们就可以直接套公式了，即枚举[0, min(n/2, m)]的x，然后计算对应的 y 的值。求出对应x*a + y*b 的最大值即可。

为什么贪心错了？

因为存在反例：如 n = 2，m = 100, a= 3, b = 2时，最优解应该是买两个2号，即有4元。

而我们的贪心车略则是如果a>b狂选1号，如果a<b狂选2号，而这里如果使用贪心，得到的却是只能组成一个1号，总价值为3元，小于最优解4元。

最后注意由于这里的数据范围是10^6，那么如果出现最终结果全为x个一号，没有二号礼包，若n取10⁶级别，x则也是10⁶级别，如果a 也是10⁶级别，则返回就是 10¹²级别了，结果是会溢出的，所以需要使用long long 来存储数据。

#include <iostream>
using namespace std;
int n, m, a, b;
typedef long long LL;
int main()
{
    cin >> n >> m >> a >> b;
    // 最终结果为x个一号，y个二号
    // 求 x*a + y*b 的max
    // 枚举
    // x的范围：[0, min(n/2, m)]
    // 则y = min(n-2*x, (m-x)/2)
    LL res = 0;
    LL t = min(n/2, m);
    for(LL x = 0; x <= t; x++) // 枚举一号礼包的个数
    {
        // 计算 y
        LL y = min(n - 2 * x, (m - x) / 2); // 计算二号礼包个数
        res = max(res, x * a + y * b);
    }
    cout << res;
    return 0;
}