游游的水果大礼包【牛客tracker 每日一题】
游游的水果大礼包
时间限制：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秒时间限制，运算开销极低。
总结
核心逻辑：枚举一号礼包的所有可行数量，对每个数量直接计算剩余资源下二号礼包的最大值，遍历所有情况得到总价值的最优解。
关键操作：资源约束推导单变量上限、固定单变量后直接取另一变量最大值、长整型存储避免数值溢出。
效率保障：单重循环百万级以内，运算量极小，代码简洁不易出错。
代码简要说明
- 变量定义：
n、m为苹果和桃子总数，a、b为两种礼包的单位价值，全部使用long long类型，避免乘积溢出。 - 枚举上限计算：
lim为一号礼包的最大可行数量，取苹果可制作数与桃子可制作数的较小值。 - 遍历求最优：
- 循环遍历一号礼包数量
x从0到lim。 - 计算剩余苹果和剩余桃子，得到当前
x下二号礼包的最大数量y。 - 计算总价值，更新全局最大值
ans。
- 循环遍历一号礼包数量
- 结果输出：遍历完成后输出最大总价值。
- 输入优化：关闭流同步并解绑 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;}