游游的水果大礼包【牛客tracker & 每日一题】

游游的水果大礼包

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

网页链接

牛客tracker

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

题目描述

游游有

n

n

n 个苹果，

m

m

m 个桃子。她可以把

2

2

2 个苹果和

1

1

1 个桃子组成价值

a

a

a 元的一号水果大礼包，也可以把

1

1

1 个苹果和

2

2

2 个桃子组成价值

b

b

b 元的二号水果大礼包。游游想知道，自己最多能组成多少价值总和的大礼包？

输入描述：

四个正整数

n

,

m

,

a

,

b

n,m,a,b

n,m,a,b ，用空格隔开。分别代表苹果的数量、桃子的数量、一号大礼包价值、二号大礼包价值。

1

≤

n

,

m

,

a

,

b

≤

10

6

1≤n,m,a,b≤10^6

1≤n,m,a,b≤106

输出描述：

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

示例1

输入：

3 4 1 2

输出：

4

说明：

组成两个二号水果大礼包，使用了

2

2

2 个苹果和

4

4

4 个桃子。总价值为

4

4

4 。

示例2

输入：

1 1 5 6

输出：

0

说明：

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

解题思路

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

1. 问题建模

设制作一号礼包

x

x

x 个、二号礼包

y

y

y 个，根据资源约束有：

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

由于两种礼包的价值均为正数，对于任意固定的

x

x

x，最优策略一定是用剩余资源制作尽可能多的二号礼包，因此无需枚举

y

y

y，可直接计算其上限。

2. 枚举策略

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

x

x

x：

• $x$
• 对每个固定的 $x$
• 此时二号礼包的最大数量为 $y=\min (n-2x,\lfloor (m-x)/2\rfloor )$
• 计算当前总价值 $x\cdot a+y\cdot b$

3. 复杂度分析

x

x

x 的枚举次数不超过

n

/

2

n/2

n/2，

n

n

n 最大为

10

6

10^6

106，总循环次数约50万次，远低于1秒时间限制，运算开销极低。

总结

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

代码简要说明

代码内容

#include <bits/stdc++.h>
using namespace std;

#define endl '\\n'
typedef long long ll;
typedef unsigned long long ull;
typedef vector<vector<ll>> vvt;
typedef pair<ll,ll> pll;
const ll N=1e3+10;
const ll INF=1e18;
const ll M=1e6+10;
const ll mod=1e9+7;

int main()
{
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;
return 0;
}