【华为OD-E卷 - 网上商城优惠活动 100分（python、java、c++、js、c）】
【华为OD-E卷 - 网上商城优惠活动 100分（python、java、c++、js、c）】
题目
某网上商场举办优惠活动，发布了满减、打折、无门槛3种优惠券，分别为：
每满100元优惠10元，无使用数限制，如100 ~ 199元可以使用1张减10元，200 ~ 299可使用2张减20元，以此类推； 92折券，1次限使用1张，如100元，则优惠后为92元; 无门槛5元优惠券，无使用数限制，直接减5元。 优惠券使用限制
每次最多使用2种优惠券，2种优惠可以叠加（优惠叠加时以优惠后的价格计算），以购物200元为例，可以先用92折券优惠到184元，再用1张满减券优惠10元，最终价格是174元，也可以用满减券2张优惠20元为180元，再使用92折券优惠到165（165.6向下取整），不同使用顺序的优惠价格不同，以最优惠价格为准。在一次购物种，同一类型优惠券使用多张时必须一次性使用，不能分多次拆开使用（不允许先使用1张满减券，再用打折券，再使用一张满减券）。 问题
请设计实现一种解决方法，帮助购物者以最少的优惠券获得最优的优惠价格。优惠后价格越低越好，同等优惠价格，使用的优惠券越少越好，可以允许某次购物不使用优惠券。 约定
优惠活动每人只能参加一次，每个人的优惠券种类和数量是一样的。
输入描述
- 第一行：每个人拥有的优惠券数量（数量取值范围为[0,10]），按满减、打折、无门槛的顺序输入 第二行：表示购物的人数n（1 ≤ n ≤ 10000） 最后n行：每一行表示某个人优惠前的购物总价格（价格取值范围(0, 1000] ，都为整数）。 约定：输入都是符合题目设定的要求的
输出描述
- 每行输出每个人每次购物优惠后的最低价格以及使用的优惠券总数量 每行的输出顺序和输入的顺序保持一致 备注 优惠券数量都为整数，取值范围为[0, 10] 购物人数为整数，取值范围为[1, 10000] 优惠券的购物总价为整数，取值范围为 (0, 1000] 优惠后价格如果是小数，则向下取整，输出都为整数
用例
用例一：
输入：
3 2 5
3
100
200
400
输出：
65 6
155 7
338 4
python解法
- 解题思路：
- 输入解析：
首先输入了四个变量 m, n, k 和 x。其中 m 是满减优惠的最大金额，n 是打折优惠的最大次数，k 是可以用来兑换免费的金额的优惠券数，x 是商品的数量。
随后输入了 x 个商品的价格。
优惠方式：
共有三种优惠方式：满减、打折、无门槛优惠券。
每种优惠方式有不同的计算规则，可以组合成不同的使用顺序。
计算每种优惠方式的最小花费：
对于每个商品，程序通过四种不同的优惠顺序来计算最终花费，并选择其中最优的方案。
先满减，再无门槛优惠券。
先打折，再无门槛优惠券。
先满减，再打折。
先打折，再满减。
每种方案都会计算出最终的花费，并根据花费的大小以及所用优惠券的数量来判断最优方案。
输出：
对于每个商品，输出最小花费和所使用的优惠券数量
# 输入商品数量和不同优惠类型的参数
m, n, k = map(int, input().split()) # m: 满减最大金额，n: 打折次数，k: 免费优惠券数
x = int(input()) # 商品数量
prices = [int(input()) for _ in range(x)] # 获取商品的价格列表
# 满减优惠
def apply_full_sub(price, m):
# 满减：每满100元减10元，最多使用m次
used = min(price // 100, m) # 使用的满减次数
return price - used * 10, used # 返回减去满减后的价格和使用的优惠券数量
# 打折优惠
def apply_discount(price, n):
# 打折：有打折券时，打9折，最多使用n次
if n > 0:
return int(price * 0.92), 1 # 打9折并返回使用打折券
return price, 0 # 没有打折券时不变，返回原价
# 免费优惠券
def apply_free(price, k):
# 免费优惠券：每5元可以兑换1张优惠券，最多使用k张
used = min(k, price // 5) # 使用的免费券数量
return max(0, price - used * 5), used # 返回最终的价格和使用的优惠券数量
# 对每个商品计算最小花费和最优优惠券使用数
for price in prices:
min_cost = price # 初始化最小花费为原价
min_coupons = 0 # 初始化最小优惠券数量
# 1. 先满减，再无门槛优惠券
cost, coupons = apply_full_sub(price, m)
cost, c = apply_free(cost, k)
if cost < min_cost or (cost == min_cost and coupons + c < min_coupons):
min_cost = cost
min_coupons = coupons + c
# 2. 先打折，再无门槛优惠券
cost, coupons = apply_discount(price, n)
cost, c = apply_free(cost, k)
if cost < min_cost or (cost == min_cost and coupons + c < min_coupons):
min_cost = cost
min_coupons = coupons + c
# 3. 先满减，再打折
cost, coupons = apply_full_sub(price, m)
cost, c = apply_discount(cost, n)
if cost < min_cost or (cost == min_cost and coupons + c < min_coupons):
min_cost = cost
min_coupons = coupons + c
# 4. 先打折，再满减
cost, coupons = apply_discount(price, n)
cost, c = apply_full_sub(cost, m)
if cost < min_cost or (cost == min_cost and coupons + c < min_coupons):
min_cost = cost
min_coupons = coupons + c
# 输出最终的最低花费和使用的优惠券数
print(f"{min_cost} {min_coupons}")
java解法
- 解题思路
- 输入解析：
m: 满减券数量，表示每满100元可减10元，最多可以使用 m 次。
n: 打折券数量，表示有打折券时可以将价格打9折，最多使用 n 次。
k: 无门槛5元券数量，表示每5元可用1张优惠券兑换，最多使用 k 张。
x: 商品数量，接着会有 x 个商品的价格。
优惠方式：
有三种类型的优惠券：满减券、打折券、无门槛5元券，每种优惠券有不同的应用规则。
需要考虑所有优惠券的组合方式，使用不同的顺序进行计算，找到每个商品的最小花费，并同时最小化所用的优惠券数量。
优化计算：
对于每个商品价格，尝试以下六种不同的优惠组合（顺序不同）：
使用满减券后再使用无门槛券
使用无门槛券后再使用满减券
使用打折券后再使用无门槛券
使用无门槛券后再使用打折券
使用满减券后再使用打折券
使用打折券后再使用满减券
对每种组合，计算出最终的花费并比较，选择最优的方案。
输出：
对于每个商品，输出最终的最小花费和所使用的优惠券数量。
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 输入满减券、打折券、无门槛券的数量，以及商品数量
int m = sc.nextInt(); // 满减券数量
int n = sc.nextInt(); // 92折券数量
int k = sc.nextInt(); // 无门槛5元券数量
int x = sc.nextInt(); // 商品数量
// 输入每个商品的价格
int[] prices = new int[x];
for (int i = 0; i < x; i++) {
prices[i] = sc.nextInt();
}
// 对每个商品计算最优的价格和优惠券使用数量
for (int price : prices) {
int[] result = calculateMinPrice(price, m, n, k);
System.out.println(result[0] + " " + result[1]);
}
}
// 计算某个商品的最小价格和使用的优惠券数
public static int[] calculateMinPrice(int price, int m, int n, int k) {
int minPrice = price; // 初始化最小价格为商品原价
int minCoupons = 0; // 初始化最小使用的优惠券数为0
// 1. 使用满减券再使用无门槛券
if (m > 0) {
int[] afterM = applyM(price, m); // 应用满减券
int[] afterK = applyK(afterM[0], k); // 在此基础上应用无门槛券
// 如果这种方式的价格更优，或者价格相同但使用的优惠券数量更少，则更新最优方案
if (afterK[0] < minPrice || (afterK[0] == minPrice && afterK[1] + afterM[1] < minCoupons)) {
minPrice = afterK[0];
minCoupons = afterK[1] + afterM[1];
}
}
// 2. 使用无门槛券再使用满减券
if (k > 0) {
int[] afterK = applyK(price, k); // 应用无门槛券
int[] afterM = applyM(afterK[0], m); // 在此基础上应用满减券
if (afterM[0] < minPrice || (afterM[0] == minPrice && afterM[1] + afterK[1] < minCoupons)) {
minPrice = afterM[0];
minCoupons = afterM[1] + afterK[1];
}
}
// 3. 使用打折券再使用无门槛券
if (n > 0) {
int[] afterN = applyN(price, n); // 应用打折券
int[] afterK = applyK(afterN[0], k); // 在此基础上应用无门槛券
if (afterK[0] < minPrice || (afterK[0] == minPrice && afterK[1] + afterN[1] < minCoupons)) {
minPrice = afterK[0];
minCoupons = afterK[1] + afterN[1];
}
}
// 4. 使用无门槛券再使用打折券
if (k > 0) {
int[] afterK = applyK(price, k); // 应用无门槛券
int[] afterN = applyN(afterK[0], n); // 在此基础上应用打折券
if (afterN[0] < minPrice || (afterN[0] == minPrice && afterN[1] + afterK[1] < minCoupons)) {
minPrice = afterN[0];
minCoupons = afterN[1] + afterK[1];
}
}
// 5. 使用满减券再使用打折券
if (m > 0) {
int[] afterM = applyM(price, m); // 应用满减券
int[] afterN = applyN(afterM[0], n); // 在此基础上应用打折券
if (afterN[0] < minPrice || (afterN[0] == minPrice && afterN[1] + afterM[1] < minCoupons)) {
minPrice = afterN[0];
minCoupons = afterN[1] + afterM[1];
}
}
// 6. 使用打折券再使用满减券
if (n > 0) {
int[] afterN = applyN(price, n); // 应用打折券
int[] afterM = applyM(afterN[0], m); // 在此基础上应用满减券
if (afterM[0] < minPrice || (afterM[0] == minPrice && afterM[1] + afterN[1] < minCoupons)) {
minPrice = afterM[0];
minCoupons = afterM[1] + afterN[1];
}
}
// 返回最优方案的最小花费和使用的优惠券数
return new int[]{minPrice, minCoupons};
}
// 应用满减券：每满100元减10元，最多使用m次
public static int[] applyM(int price, int m) {
int count = Math.min(price / 100, m); // 计算满减券使用次数
return new int[]{price - count * 10, count}; // 返回使用后的价格和使用的满减券数量
}
// 应用打折券：有打折券时打9折，最多使用n次
public static int[] applyN(int price, int n) {
if (n > 0) {
return new int[]{(int) Math.floor(price * 0.92), 1}; // 打9折并返回使用的打折券数量
}
return new int[]{price, 0}; // 如果没有打折券，则返回原价
}
// 应用无门槛5元券：每5元使用1张券，最多使用k张
public static int[] applyK(int price, int k) {
int used = Math.min(price / 5, k); // 计算使用的无门槛5元券数量
return new int[]{Math.max(0, price - used * 5), used}; // 返回应用后的价格和使用的无门槛券数量
}
}
C++解法
- 解题思路
更新中
C解法
更新中
JS解法
第一行输入是四个整数 a、b、c 和 d，其中：
a：满减券数量，每个满减券能减10元，最大能减 a 次。
b：打折券数量，最多使用 b 次，每次可以打9折。
c：无门槛5元券数量，最多使用 c 次，每次减少5元。
d：商品的数量，接下来会有 d 个商品的价格。
接下来的 d 行输入每个商品的价格。
计算商品的最小花费：
对于每个商品的价格，尝试不同的优惠组合，计算最小的花费：
使用满减券后再使用打折券、无门槛券。
使用打折券后再使用满减券、无门槛券。
使用无门槛券后再使用满减券、打折券。
通过不同的优惠顺序，找到每个商品的最优花费和使用的优惠券数。
输出：
对每个商品，输出最小花费和所使用的优惠券数量。
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
const data = []; // 用于保存所有输入的数据
let a, b, c, d; // 满减券、打折券、无门槛券的数量以及商品数量
// 监听输入的每一行
rl.on("line", (line) => {
data.push(line); // 将输入的每一行保存到数据数组中
// 解析第一行数据：a, b, c, d
if (data.length === 1) {
[a, b, c] = data[0].split(" ").map(Number); // 使用map转换成整数
}
// 解析第二行数据：d
if (data.length === 2) {
d = parseInt(data[1]); // 商品的数量
}
// 当接收到商品数量的数据时，开始处理商品价格
if (d && data.length === d + 2) {
data.shift(); // 删除第一行（包含优惠券数和商品数量的数据）
data.shift(); // 删除第二行（包含商品数量的行）
const prices = data.map(Number); // 将商品价格列表转换为数字数组
// 调用getRes函数计算每个商品的最优价格和优惠券使用情况
getRes(prices, a, b, c);
data.length = 0; // 清空数据数组，准备下一轮输入
}
});
// 计算每个商品的最小花费和使用的优惠券数
function getRes(prices, a, b, c) {
for (let p of prices) { // 遍历所有商品的价格
const res = []; // 用于存储不同优惠组合后的结果
// 1. 使用满减券再使用打折券
const m1 = useM(p, a);
const mn1 = useN(m1[0], b); // 使用打折券
res.push([mn1[0], a + b - (m1[1] + mn1[1])]); // 记录最终价格和使用的优惠券数
// 2. 使用满减券再使用无门槛券
const mk1 = useK(m1[0], c);
res.push([mk1[0], a + c - (m1[1] + mk1[1])]);
// 3. 使用打折券再使用满减券
const n1 = useN(p, b); // 先应用打折券
const nm1 = useM(n1[0], a); // 再应用满减券
res.push([nm1[0], b + a - (n1[1] + nm1[1])]);
// 4. 使用打折券再使用无门槛券
const nk1 = useK(n1[0], c);
res.push([nk1[0], b + c - (n1[1] + nk1[1])]);
// 按价格升序排序，如果价格相同，按照使用的优惠券数升序排序
res.sort((x, y) => (x[0] === y[0] ? x[1] - y[1] : x[0] - y[0]));
// 输出最优结果
console.log(res[0].join(" "));
}
}
// 满减券使用函数：每满100元减10元，最多使用a次
function useM(p, a) {
const cnt = Math.floor(p / 100); // 计算可以使用的满减券次数
const used = Math.min(a, cnt); // 使用的次数不能超过a
p -= used * 10; // 计算应用满减后的价格
a -= used; // 更新剩余的满减券数量
return [p, a]; // 返回应用满减后的价格和剩余的满减券数量
}
// 打折券使用函数：打9折，最多使用b次
function useN(p, b) {
if (b >= 1) {
p = Math.floor(p * 0.92); // 打9折
}
return [p, b - 1]; // 返回打折后的价格和剩余的打折券数量
}
// 无门槛5元券使用函数：每5元使用1张券，最多使用c次
function useK(p, c) {
while (p > 0 && c > 0) { // 只要价格大于0且还有优惠券
p -= 5; // 每次减少5元
p = Math.max(p, 0); // 确保价格不为负数
c--; // 更新剩余的无门槛券数量
}
return [p, c]; // 返回使用后的价格和剩余的无门槛券数量
}
注意：
如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏