游游的水果大礼包时间限制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 n2xy≤n桃子约束x 2 y ≤ m x 2y \le mx2y≤m目标最大化总价值a ⋅ x b ⋅ y a \cdot x b \cdot ya⋅xb⋅y由于两种礼包的价值均为正数对于任意固定的x xx最优策略一定是用剩余资源制作尽可能多的二号礼包因此无需枚举y yy可直接计算其上限。2. 枚举策略枚举一号礼包的所有可能数量x xxx 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)ymin(n−2x,⌊(m−x)/2⌋)。计算当前总价值x ⋅ a y ⋅ b x \cdot a y \cdot bx⋅ay⋅b更新全局最大值。3. 复杂度分析x xx的枚举次数不超过n / 2 n/2n/2n nn最大为10 6 10^6106总循环次数约50万次远低于1秒时间限制运算开销极低。总结核心逻辑枚举一号礼包的所有可行数量对每个数量直接计算剩余资源下二号礼包的最大值遍历所有情况得到总价值的最优解。关键操作资源约束推导单变量上限、固定单变量后直接取另一变量最大值、长整型存储避免数值溢出。效率保障单重循环百万级以内运算量极小代码简洁不易出错。代码简要说明变量定义n、m为苹果和桃子总数a、b为两种礼包的单位价值全部使用long long类型避免乘积溢出。枚举上限计算lim为一号礼包的最大可行数量取苹果可制作数与桃子可制作数的较小值。遍历求最优循环遍历一号礼包数量x从0到lim。计算剩余苹果和剩余桃子得到当前x下二号礼包的最大数量y。计算总价值更新全局最大值ans。结果输出遍历完成后输出最大总价值。输入优化关闭流同步并解绑 tie提升输入读取效率。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll n,m,a,b;cinnmab;ll ans0;ll limmin(n/2,m);for(ll x0;xlim;x){ll ymin(n-2*x,(m-x)/2);ansmax(ans,x*ay*b);}coutansendl;return0;}