华为OD机试之模拟商场优惠打折（Java源码）

模拟商场优惠打折

题目描述

模拟商场优惠打折，有三种优惠券可以用，满减券、打折券和无门槛券。
满减券：满100减10，满200减20，满300减30，满400减40，以此类推不限制使用；
打折券：固定折扣92折，且打折之后向下取整，每次购物只能用1次；
无门槛券：一张券减5元，没有使用限制。
每个人结账使用优惠券时有以下限制：

每人每次只能用两种优惠券，并且同一种优惠券必须一次用完，不能跟别的穿插使用（比如用一张满减，再用一张打折，再用一张满减，这种顺序不行）。
求不同使用顺序下每个人用完券之后得到的最低价格和对应使用优惠券的总数；如果两种顺序得到的价格一样低，就取使用优惠券数量较少的那个。

输入描述

第一行三个数字m,n,k，分别表示每个人可以使用的满减券、打折券和无门槛券的数量;
第二行一个数字x, 表示有几个人购物;
后面x行数字，依次表示是这几个人打折之前的商品总价。

输出描述

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

用例

输入

3 2 5
3
100
200
400

输出

65 6
135 8
275 8

说明

输入：

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

输出：

第一个人使用 1 张满减券和5张无门槛券价格最低。（100-10=90, 90-5*5=65）

第二个人使用 3 张满减券和5张无门槛券价格最低。（200-20-10-10=160, 160 – 5*5 = 135）

第二个人使用 3 张满减券和5张无门槛券价格最低。（400-40-30-30=300, 300 – 5*5=275）

源码和解析
解析：

这个题其是暴力求解即可，因为只有三种券且每次只能使用2种。因此按使用顺序不同可以得到6种计算方式。分别对用户输入的价格进行每种方式求解后取最优值即可。
思考？如果券种类多一点，每次使用的数量多一点。那么组合方式就很难，暴力破解就无法了。

示例代码：

import java.util.Scanner;

public class T36 {
	static int mjq;
	static int dzq;
	static int wmkq;

	static class Group {
		int price;// 打折后价格
		int num;// 优惠券使用熟练
	}

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		String input = scanner.nextLine();
		mjq = Integer.parseInt(input.split(" ")[0]);// 满减券数量 100减10 200减20
													// 300减30
		dzq = Integer.parseInt(input.split(" ")[1]); // 打折券数量 92折 向下取整
		wmkq = Integer.parseInt(input.split(" ")[2]); // 无门槛券 减5元 价格>=0
		int nums = Integer.parseInt(scanner.nextLine());
		for (int i = 0; i < nums; i++) {
			int price = Integer.parseInt(scanner.nextLine());
			Group g = getMinPrice(price);
			System.out.println(g.price + " " + g.num);
		}

	}

	public static Group getMinPrice(int price) {
		String ways[] = { "MD", "MY", "DM", "DY", "YM", "YD" };
		Group group = new Group();
		group.price = price;
		group.num = dzq + mjq + wmkq;
		for (String way : ways) {
			Group g = count(way, price);
			if (g.price < group.price) {
				group.price = g.price;
				group.num = g.num;
			} else if (g.price == group.price) {
				if (g.num < group.num) {
					group.num = g.num;
				}
			}
		}
		return group;
	}

	public static Group count(String way, int price) {
		// Map<Integer, Integer> map = new HashMap<Integer, Integer>(); // 价格
		// 和数量
		Group group = new Group();
		int mjCount = 0;// 满减券使用数量
		int wmqCount = 0;// 优惠券使用数量
		switch (way) {
		case "MD":
			// 先满减 再打折
			while (mjCount < mjq && price >= 100) {
				int num = (int) (price / 100) * 10;
				// System.out.println(price+"_"+num);
				price -= num;
				mjCount++;
			}
			// System.out.println("满减后的价格" + price);
			price = (int) (price * 0.92);
			// System.out.println("打折后的价格" + price);
			group.price = price;
			group.num = mjCount + 1;
			break;
		case "MY":
			// 先满减 无门槛券
			while (mjCount < mjq && price >= 100) {
				int num = (int) (price / 100) * 10;
				// System.out.println(price+"_"+num);
				price -= num;
				mjCount++;
			}
			// System.out.println("满减后的价格" + price);
			while (price > 0 && wmqCount < wmkq) {
				price -= 5;
				price = price < 0 ? 0 : price;
				wmqCount++;
			}
			group.price = price;
			group.num = mjCount + wmqCount;
			// System.out.println("无门槛后的价格" + price);
			break;
		case "DM":
			// 先打折再满减
			price = (int) (price * 0.92);
			// 先满减 再打折
			// System.out.println("打折后的价格" + price);
			while (mjCount < mjq && price >= 100) {
				int num = (int) (price / 100) * 10;
				// System.out.println(price+"_"+num);
				price -= num;
				mjCount++;
			}
			// System.out.println("满减后的价格" + price);
			group.price = price;
			group.num = mjCount + 1;
			break;
		case "DY":
			// 先打折 再使用无门槛券
			price = (int) (price * 0.92);
			// System.out.println("打折后的价格" + price);
			while (price > 0 && wmqCount < wmkq) {
				price -= 5;
				price = price < 0 ? 0 : price;
				wmqCount++;
			}
			// System.out.println("无门槛券后的价格" + price);
			group.price = price;
			group.num = wmqCount + 1;
			break;
		case "YM":
			// 先使用无门槛券 再满减
			while (price > 0 && wmqCount < wmkq) {
				price -= 5;
				wmqCount++;
				price = price < 0 ? 0 : price;
			}
			// System.out.println("无门槛券后的价格" + price);
			while (mjCount < mjq && price >= 100) {
				int num = (int) (price / 100) * 10;
				price -= num;
				mjCount++;
			}
			// System.out.println("满减后的价格" + price);
			group.price = price;
			group.num = mjCount + wmqCount;
			break;
		case "YD":
			// 先使用 无门槛券 再使用打折
			while (price > 0 && wmqCount < wmkq) {
				price -= 5;
				wmqCount++;
				price = price < 0 ? 0 : price;
			}
			// System.out.println("无门槛券后的价格" + price);
			price = (int) (price * 0.92);
			// System.out.println("打折后的价格" + price);
			group.price = price;
			group.num = wmqCount + 1;
		default:
			break;
		}
		return group;
	}
}