目录

题目描述

输入描述

输出描述

用例

题目解析

算法源码

题目描述

模拟商场优惠打折，有三种优惠券可以用，满减券、打折券和无门槛券。

满减券：满100减10，满200减20，满300减30，满400减40，以此类推不限制使用；

打折券：固定折扣92折，且打折之后向下取整，每次购物只能用1次；

无门槛券：一张券减5元，没有使用限制。

每个人结账使用优惠券时有以下限制：

每人每次只能用两种优惠券，并且同一种优惠券必须一次用完，不能跟别的穿插使用（比如用一张满减，再用一张打折，再用一张满减，这种顺序不行）。

求不同使用顺序下每个人用完券之后得到的最低价格和对应使用优惠券的总数；如果两种顺序得到的价格一样低，就取使用优惠券数量较少的那个。

输入描述

第一行三个数字m,n,k，分别表示每个人可以使用的满减券、打折券和无门槛券的数量;

第二行一个数字x, 表示有几个人购物;

后面x行数字，依次表示是这几个人打折之前的商品总价。

输出描述

输出每个人使用券之后的最低价格和对应使用优惠券的数量

用例

题目解析

本题的解题思路如下，首先实现满减，打折，无门槛的逻辑：

• 满减逻辑，只要总价price大于等于100，且还有满减券，则不停price -= Math.floor(price / 100) * 10; 直到总价price小于100，或者满减券用完。
• 打折逻辑，按照题目意思，打折券只能使用一次，因此无论打折券有多少张，都只能使用一次，因此只要打折券数量大于等于1，那么price = Math.floor(price * 0.92);
• 无门槛逻辑，只要总价price大于0，且还有无门槛券，则不停price -= 5; 直到price小于等于0，或者无门槛券用完。

接下来就是求上面三种逻辑的任选2个的排列：

假设满减是M，打折是N，无门槛是K，则有排列如下：

• MN、NM
• MK、KM
• NK、KN

注意，券的使用对顺序敏感。

因此，求出以上排列后，对每个人的总价使用六种方式减价，只保留减价最多，用券最少的那个。

算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");const rl = readline.createInterface({input: process.stdin,output: process.stdout,
});const lines = [];
let m, n, k, x;
rl.on("line", (line) => {lines.push(line);if (lines.length === 1) {[m, n, k] = lines[0].split(" ").map(Number);}if (lines.length === 2) {x = parseInt(lines[1]);}if (x && lines.length === x + 2) {lines.shift();lines.shift();const arr = lines.map(Number);getResult(arr, m, n, k);lines.length = 0;}
});/**** @param {*} arr 几个人打折之前的商品总价* @param {*} m 满减券数量* @param {*} n 打折券数量* @param {*} k 无门槛券数量*/
function getResult(arr, m, n, k) {const operations = [[M, m],[N, n],[K, k],];for (let price of arr) {const res = [];dfs(operations, new Array(3), [], res, price);res.sort((a, b) => (a[0] !== b[0] ? a[0] - b[0] : a[1] - b[1]));const ans = res[0];console.log(ans.join(" "));}
}function dfs(operations, used, path, res, price) {if (path.length === 2) {const [p1, p2] = path;const [op1, c1] = p1;const [op2, c2] = p2;const [remain_price1, remain_count1] = op1(price, c1);const [remain_price2, remain_count2] = op2(remain_price1, c2);res.push([remain_price2, c1 + c2 - remain_count1 - remain_count2]);return;}for (let i = 0; i < operations.length; i++) {if (!used[i]) {path.push(operations[i]);used[i] = true;dfs(operations, used, path, res, price);used[i] = false;path.pop();}}
}// 满减
function M(price, m) {while (price >= 100 && m > 0) {price -= Math.floor(price / 100) * 10;m--;}return [price, m];
}// 打折
function N(price, n) {if (n >= 1) {price = Math.floor(price * 0.92);}return [price, 1];
}// 无门槛
function K(price, k) {while (price > 0 && k > 0) {price -= 5;k--;}return [price, k];
}