游游的水果大礼包

时间限制：1秒 空间限制：256M

网页链接

牛客tracker

牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！

题目描述

游游有n nn个苹果，m mm个桃子。她可以把2 22个苹果和1 11个桃子组成价值a aa元的一号水果大礼包，也可以把1 11个苹果和2 22个桃子组成价值b bb元的二号水果大礼包。游游想知道，自己最多能组成多少价值总和的大礼包？

输入描述：

四个正整数n , m , a , b n,m,a,bn,m,a,b，用空格隔开。分别代表苹果的数量、桃子的数量、一号大礼包价值、二号大礼包价值。
1 ≤ n , m , a , b ≤ 10 6 1≤n,m,a,b≤10^61≤n,m,a,b≤106

输出描述：

一个整数，代表大礼包的最大价值总和。

示例1

输入：

3 4 1 2

输出：

4

说明：

组成两个二号水果大礼包，使用了2 22个苹果和4 44个桃子。总价值为4 44。

示例2

输入：

1 1 5 6

输出：

0

说明：

显然无法组合成任意一个大礼包

解题思路

本题是有限资源下的双物品组合优化问题，通过枚举其中一种礼包的数量，快速推导另一种礼包的最大可行数量，遍历所有情况取价值最大值，实现简单且效率充足。

1. 问题建模

设制作一号礼包x xx个、二号礼包y yy个，根据资源约束有：

• 苹果约束：2 x + y ≤ n 2x + y \le n2x+y≤n
• 桃子约束：x + 2 y ≤ m x + 2y \le mx+2y≤m
• 目标：最大化总价值a ⋅ x + b ⋅ y a \cdot x + b \cdot ya⋅x+b⋅y

由于两种礼包的价值均为正数，对于任意固定的x xx，最优策略一定是用剩余资源制作尽可能多的二号礼包，因此无需枚举y yy，可直接计算其上限。

2. 枚举策略

枚举一号礼包的所有可能数量x xx：

• x xx的上限为min ⁡ ( ⌊ n / 2 ⌋ , m ) \min(\lfloor n/2 \rfloor, m)min(⌊n/2⌋,m)：每个一号礼包消耗2个苹果、1个桃子，因此分别受苹果总数和桃子总数限制。
• 对每个固定的x xx，剩余苹果数为n − 2 x n-2xn−2x，剩余桃子数为m − x m-xm−x。
• 此时二号礼包的最大数量为y = min ⁡ ( n − 2 x , ⌊ ( m − x ) / 2 ⌋ ) y = \min(n-2x,\ \lfloor (m-x)/2 \rfloor)y=min(n−2x,⌊(m−x)/2⌋)。
• 计算当前总价值x ⋅ a + y ⋅ b x \cdot a + y \cdot bx⋅a+y⋅b，更新全局最大值。

3. 复杂度分析

x xx的枚举次数不超过n / 2 n/2n/2，n nn最大为10 6 10^6106，总循环次数约50万次，远低于1秒时间限制，运算开销极低。

总结

核心逻辑：枚举一号礼包的所有可行数量，对每个数量直接计算剩余资源下二号礼包的最大值，遍历所有情况得到总价值的最优解。
关键操作：资源约束推导单变量上限、固定单变量后直接取另一变量最大值、长整型存储避免数值溢出。
效率保障：单重循环百万级以内，运算量极小，代码简洁不易出错。

代码简要说明

1. 变量定义：n、m为苹果和桃子总数，a、b为两种礼包的单位价值，全部使用long long类型，避免乘积溢出。
2. 枚举上限计算：lim为一号礼包的最大可行数量，取苹果可制作数与桃子可制作数的较小值。
3. 遍历求最优：
   • 循环遍历一号礼包数量x从0到lim。
   • 计算剩余苹果和剩余桃子，得到当前x下二号礼包的最大数量y。
   • 计算总价值，更新全局最大值ans。
4. 结果输出：遍历完成后输出最大总价值。
5. 输入优化：关闭流同步并解绑 tie，提升输入读取效率。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll n,m,a,b;cin>>n>>m>>a>>b;ll ans=0;ll lim=min(n/2,m);for(ll x=0;x<=lim;x++){ll y=min(n-2*x,(m-x)/2);ans=max(ans,x*a+y*b);}cout<<ans<<endl;return0;}