你他妈找茬是吧
1027 字
5 分钟
你他妈找茬是吧
题目描述
小红开了一家水果店。已知小红进货时,一个桃子需要 元,一个篮子需要 元。小红只能在开始卖桃子之前进货,且她只有 元,进货商只有 个桃子。
给定一个正整数 ,小红预知到今天共有 个顾客,他们的需求用两个长为 的数组 、 () 表示,第 名顾客希望用 元购买 个桃子,且需要 个篮子。 特殊的,保证对于所有的 ,,即不会存在亏本生意。
请你帮小红计算,以最优的方式进货,她今天最多能够获得多少元(不计算支出)。
输入描述:
第一行输入五个整数 (),代表桃子的价格、篮子的价格、小红拥有的钱、进货商的桃子数量、顾客购买的数量。 第二行输入一个整数 ()。 第三行输入 个整数 ()。 第四行输入 个整数 ()。
输出描述:
输出一个整数,代表小红今天最多能获得的钱数。
代码:
#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;}
文章分享
如果这篇文章对你有帮助,欢迎分享给更多人!




