C++ 幸运茶饮料店分组策略：最大化收益

C++ 幸运茶饮料店分组策略：最大化收益$happy$ 猫的茶饮店新推出了幸运茶，为了吸引顾客，$happy$ 猫准备了一个时长为 $n$ 天的活动。活动前，有 $m$ 名顾客预约，但 $happy$ 猫每天只能做一定量的奶茶，且奶茶份量每天都不一样。顾客按照预约顺序分成 $n$ 组，每组顾客在对应的一天购买奶茶。活动期间有以下福利：1. 每天最后一位顾客购买奶茶免费。2. 每天第一位顾客免费获得一杯幸运茶，但有些顾客会拒绝幸运茶，这时幸运茶会推给下一位购买的顾客。每位顾客对幸运茶的态度不同，喜爱度分为 $4$ 类：* $3$：特别喜欢幸运茶，收到后会高兴地买一杯奶茶。* $2$：蹭幸运茶，收到后会立刻消失。* $1$：礼貌地婉拒幸运茶，并购买一杯奶茶。* $0$：对幸运茶恨之入骨，自动推给下一位顾客。$happy$ 猫希望你帮他制定一个最佳的分组策略，使得这 $n$ 天的收益最大化。输入格式：输入共 $m+n+1$ 行。第 $1$ 行输入 $n$, $m$, $p$, $k$, $r$。 $n$：活动天数。 $m$：预约顾客数。 $p$：幸运茶的成本。 $k$：每杯奶茶的纯收益。* $r$：每杯奶茶的成本。第 $2$ ~ $m+1$ 行，第 $i+1$ 行输入第 $i$ 个顾客的喜爱度。第 $m+2$ ~ $m+n+1$ 行，第 $i+m+1$ 行输入第 $i$ 天的奶茶数。**输出格式：输出这 $n$ 天的最大收益（可能为负数）。样例输入 #1：暂无样例输出 #1：暂无提示： $1 /le n /le m /le 10^2$ $1 /le p, k, r /le 10^5$**C++ 解法：**cpp#include #include using namespace std;int main() { int n, m, p, k, r; cin >> n >> m >> p >> k >> r; vector love(m); vector tea(n); for (int i = 0; i < m; i++) { cin >> love[i]; } for (int i = 0; i < n; i++) { cin >> tea[i]; } int maxProfit = -1; for (int i = 0; i <= n; i++) { int profit = 0; int teaLeft = 0; for (int j = 0; j < i; j++) { profit += love[j] * k; teaLeft += tea[j]; } int customersLeft = m - i; int freeTea = customersLeft > 0 ? teaLeft / customersLeft : 0; profit -= freeTea * p; if (customersLeft > 0) { for (int j = i; j < n; j++) { teaLeft -= tea[j]; customersLeft--; if (customersLeft == 0) { break; } int loveLevel = love[j]; if (loveLevel == 3) { profit += k - p; } else if (loveLevel == 2) { continue; } else if (loveLevel == 1) { profit += k; } else { profit -= r; } } } maxProfit = max(maxProfit, profit); } cout << maxProfit << endl; return 0;}**解法思路：**这个解法使用了一个双层循环，外层循环枚举分组的数量，内层循环计算每种分组方案的收益。对于每种分组方案，先计算前 $i$ 个顾客的收益，然后计算剩余顾客的收益。剩余顾客的收益根据他们的喜爱度和幸运茶处理规则进行计算。最后，比较所有分组方案的收益，取最大值。**时间复杂度：**该解法的时间复杂度为 $O(n*m)$，其中 $n$ 为天数，$m$ 为顾客数。