视频加载失败

你他妈找茬是吧

1027 字
5 分钟
你他妈找茬是吧

题目描述#

小红开了一家水果店。已知小红进货时,一个桃子需要 xx 元,一个篮子需要 yy 元。小红只能在开始卖桃子之前进货,且她只有 ss 元,进货商只有 mm 个桃子。

给定一个正整数 kk,小红预知到今天共有 nn 个顾客,他们的需求用两个长为 nn 的数组 a1,a2,…,ana_1, a_2, \dots, a_n、b1,b2,…,bnb_1, b_2, \dots, b_n (bi∈{0,1}b_i \in \{0, 1\}) 表示,第 ii 名顾客希望用 aia_i 元购买 kk 个桃子,且需要 bib_i 个篮子。 特殊的,保证对于所有的 i∈[1,n]i \in [1, n],k×x+bi×y<aik \times x + b_i \times y < a_i,即不会存在亏本生意。

请你帮小红计算,以最优的方式进货,她今天最多能够获得多少元(不计算支出)。

输入描述:#

第一行输入五个整数 x,y,s,m,kx, y, s, m, k (1≤x,y,s,m,k≤1091 \le x, y, s, m, k \le 10^9),代表桃子的价格、篮子的价格、小红拥有的钱、进货商的桃子数量、顾客购买的数量。 第二行输入一个整数 nn (1≤n≤2×1051 \le n \le 2 \times 10^5)。 第三行输入 nn 个整数 a1,a2,…,ana_1, a_2, \dots, a_n (1≤ai≤1091 \le a_i \le 10^9)。 第四行输入 nn 个整数 b1,b2,…,bnb_1, b_2, \dots, b_n (bi∈{0,1}b_i \in \{0, 1\})。

输出描述:#

输出一个整数,代表小红今天最多能获得的钱数。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main()
{
// 定义变量
ll p; // 无实际作用,未使用
ll x, y, s, m, k; // x:桃子进价, y:篮子进价, s:总预算, m:桃子总库存, k:每个顾客需要的桃子数
ll n; // 顾客数量
// 输入基本参数
cin >> x >> y >> s >> m >> k;
cin >> n;
// a[i] 存储第 i 个顾客愿意支付的钱,b[i] 存储第 i 个顾客是否需要篮子
vector<ll> a(n), b(n);
vector<ll> n1, n2; // n1: 需要篮子的顾客,n2: 不需要篮子的顾客
// 读入每个顾客的支付金额
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
// 读入每个顾客是否需要篮子 (0 或 1)
for (int i = 0; i < n; i++)
{
cin >> b[i];
}
// 将顾客按是否需要篮子分成两组
for (int i = 0; i < n; i++)
{
if (b[i] == 1)
{
n1.push_back(a[i]); // 需要篮子的顾客
}
else
{
n2.push_back(a[i]); // 不需要篮子的顾客
}
}
// 对两组顾客的支付金额从大到小排序(贪心:优先服务出价高的顾客)
sort(n1.rbegin(), n1.rend());
sort(n2.rbegin(), n2.rend());
// 构建前缀和数组,n11[i] 表示 n1 中前 i 个顾客的支付总额
// n22[i] 表示 n2 中前 i 个顾客的支付总额
vector<ll> n11(n1.size() + 1);
vector<ll> n22(n2.size() + 1);
for (int i = 0; i < n1.size(); i++)
{
n11[i + 1] = n11[i] + n1[i];
}
for (int i = 0; i < n2.size(); i++)
{
n22[i + 1] = n22[i] + n2[i];
}
ll ans = 0; // 记录最大收益
// 枚举服务需要篮子的顾客数量 i(从 0 到 n1.size())
for (int i = 0; i <= n1.size(); i++)
{
// 如果预算不够买 i 个篮子,则后续更大的 i 更不可能,直接跳出
if (s < i * y)
{
break;
}
// 计算买完 i 个篮子后剩余的预算
ll rem = s - i * y;
// 用剩余预算最多能买多少个桃子
ll max_peach_buy = rem / x;
// 不能超过进货商的桃子总量 m
max_peach_buy = min(max_peach_buy, m);
// 这些桃子最多能服务多少位顾客(每位顾客需要 k 个桃子)
ll total_max_customer = max_peach_buy / k;
// 如果服务的总顾客数都少于需要篮子的顾客数,则当前 i 不合法
if (total_max_customer < i)
continue;
// 扣除服务需要篮子的顾客后,还能服务多少不需要篮子的顾客
ll can_n22 = total_max_customer - i;
// 不能超过实际不需要篮子的顾客数量
can_n22 = min(can_n22, (ll)n2.size());
// 当前方案的总收益 = 服务 i 个需要篮子的顾客收益 + 服务 can_n22 个不需要篮子的顾客收益
ll cur = n11[i] + n22[can_n22];
// 更新最大收益
ans = max(ans, cur);
}
// 输出最大收益
cout << ans << endl;
return 0;

}

文章分享

如果这篇文章对你有帮助,欢迎分享给更多人!

你他妈找茬是吧
https://www.xiaobaibai454.top/posts/xuexi1/
作者
Xiao_baibai
发布于
2026-10-07
许可协议
CC BY-NC-SA 4.0

评论区

Profile Image of the Author
Xiao_baibai
你是怎么找到这里的???
分类
最新动态
站点统计
文章
25
分类
4
标签
5
总字数
17,871
运行时长
0 天
最后活动
0 天前
站点信息
构建平台
GitHub Actions
博客版本
Firefly v6.16.8
文章许可
CC BY-NC-SA 4.0
文章目录