模拟商场优惠打折，有三种优惠券可以用，满减券、打折券和无门槛券。
满减券：满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）
该问题可以被视为动态规划（Dynamic Programming, DP）问题。
首先，我们需要创建一个数组dp，其大小是可能的最大商品价格，也就是最大可用的优惠券的10倍（以10为单位因为满减券的门槛是100元）。dp[j]表示达到价格j需要使用的最小优惠券数量。初始化dp数组，除了dp[price]设为0外，其他全部设为无穷大（这里我们用常量MAX_COUPONS表示）。
然后，对每个购物者的商品总价，我们首先尝试使用满减券和无门槛券。对于满减券，我们检查是否满足满减条件（100元），如果满足，我们就更新dp数组。对于无门槛券，只要其数量大于0，我们就可以使用，同样更新dp数组。
使用满减券和无门槛券后，我们查找dp数组，寻找最小的可能价格，同时记录所需的优惠券数量。
最后，我们检查是否可以使用打折券。如果打折后的价格低于使用满减券和无门槛券后的最小价格，我们就选择使用打折券，并增加使用的优惠券数量。
时间复杂度：对每个购物者，我们需要遍历其商品总价次，而对于满减券，我们需要在每个价格上遍历满减券的数量，所以总的时间复杂度是O(nmprice)，其中n是购物者的数量，m是满减券的数量，price是商品总价。
空间复杂度：我们需要一个大小为MAX_PRICE的数组来保存状态，所以空间复杂度是O(MAX_PRICE)。
#include <stdio.h>
#include <stdlib.h>
#define MAXN 10005
#define INF 1e9
#define MIN(a, b) ((a) < (b) ? (a) : (b))
int dp[MAXN], prices[MAXN], m, n, k, x;
// 使用满减券和无门槛券，找到最低价格和使用的优惠券数量
void get_discount_with_full_reduction_and_no_threshold(int price, int* min_price, int* num_coupons) {
int i, j, cost, cnt;
for (i = 0; i <= price; ++i) {
dp[i] = INF;
}
dp[price] = 0;
for (i = price; i >= 10; --i) {
// 使用满减券
for (j = 1; j <= m && j * 100 <= i; ++j) {
cost = i - j * 10;
cnt = dp[i] + j;
if (dp[cost] > cnt) {
dp[cost] = cnt;
}
}
// 使用无门槛券
if (k && i >= 5) {
cost = i - 5;
cnt = dp[i] + 1;
if (dp[cost] > cnt) {
dp[cost] = cnt;
}
}
}
for (i = 0; i <= price; ++i) {
if (dp[i] <= k) {
*min_price = i;
*num_coupons = dp[i];
return;
}
}
}
// 使用打折券，找到最低价格和使用的优惠券数量
void get_discount_with_discount_coupon(int price, int* min_price, int* num_coupons) {
int new_price = price * 0.92;
if (new_price < *min_price) {
*min_price = new_price;
*num_coupons += 1;
}
}
int main() {
int i, min_price, num_coupons;
scanf("%d %d %d", &m, &n, &k);
scanf("%d", &x);
for (i = 0; i < x; ++i) {
scanf("%d", &prices[i]);
}
for (i = 0; i < x; ++i) {
get_discount_with_full_reduction_and_no_threshold(prices[i], &min_price, &num_coupons);
if (n) {
get_discount_with_discount_coupon(prices[i], &min_price, &num_coupons);
}
printf("%d %d\n", min_price, num_coupons);
}
return 0;
}
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX_PRICE 10005
#define MAX_COUPONS 105
int dp[MAX_PRICE];
int main() {
int m, n, k, x;
cin >> m >> n >> k >> x;
vector<int> prices(x);
for(int i=0; i<x; ++i){
cin >> prices[i];
}
for(int i=0; i<x; ++i){
int price = prices[i];
for(int j=0; j<=price; ++j){
dp[j] = MAX_COUPONS;
}
dp[price] = 0;
// 满减券和无门槛券
for(int j=price; j>=10; --j){
// 使用满减券
for(int l=1; l<=m && l*100 <= j; ++l){
dp[j - l*10] = min(dp[j - l*10], dp[j] + l);
}
// 使用无门槛券
if(j>=5 && k){
dp[j-5] = min(dp[j-5], dp[j] + 1);
}
}
int min_price = price, min_coupons = dp[0];
for(int j=0; j<price; ++j){
if(dp[j]<=k){
min_price = j;
min_coupons = dp[j];
break;
}
}
// 打折券
if(n){
if(price*0.92 < min_price){
min_price = price*0.92;
min_coupons += 1;
}
}
cout << min_price << " " << min_coupons << endl;
}
return 0;
}
import java.util.*;
public class Main {
private static final int MAX_PRICE = 10005;
private static final int MAX_COUPONS = 105;
private static int[] dp = new int[MAX_PRICE];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int m = sc.nextInt();
int n = sc.nextInt();
int k = sc.nextInt();
int x = sc.nextInt();
int[] prices = new int[x];
for (int i = 0; i < x; i++) {
prices[i] = sc.nextInt();
}
for (int i = 0; i < x; i++) {
int price = prices[i];
Arrays.fill(dp, MAX_COUPONS);
dp[price] = 0;
// Full Reduction and No Threshold coupons
for (int j = price; j >= 10; --j) {
// Using Full Reduction coupons
for (int l = 1; l <= m && l * 100 <= j; ++l) {
dp[j - l * 10] = Math.min(dp[j - l * 10], dp[j] + l);
}
// Using No Threshold coupons
if (j >= 5 && k > 0) {
dp[j - 5] = Math.min(dp[j - 5], dp[j] + 1);
}
}
int minPrice = price;
int minCoupons = dp[0];
for (int j = 0; j < price; ++j) {
if (dp[j] <= k) {
minPrice = j;
minCoupons = dp[j];
break;
}
}
// Discount coupons
if (n > 0 && price * 0.92 < minPrice) {
minPrice = (int) (price * 0.92);
minCoupons += 1;
}
System.out.println(minPrice + " " + minCoupons);
}
}
}
import sys
def calculate_min_price_and_coupons(m, n, k, x, prices):
MAX_PRICE = 10005
MAX_COUPONS = 105
dp = [0] + [MAX_COUPONS]*MAX_PRICE
res = []
for price in prices:
dp = [0]*(price + 1) + [MAX_COUPONS]*(MAX_PRICE - price)
# Full Reduction and No Threshold coupons
for i in range(price, 9, -1):
# Using Full Reduction coupons
for j in range(1, min(i // 100, m) + 1):
dp[i - j*10] = min(dp[i - j*10], dp[i] + j)
# Using No Threshold coupons
if k > 0 and i >= 5:
dp[i - 5] = min(dp[i - 5], dp[i] + 1)
min_price = price
min_coupons = MAX_COUPONS
for i in range(price + 1):
if dp[i] <= k:
min_price = i
min_coupons = dp[i]
break
# Discount coupons
if n > 0:
discount_price = int(price * 0.92)
if discount_price < min_price:
min_price = discount_price
min_coupons += 1
res.append((min_price, min_coupons))
return res
m, n, k = map(int, input().split())
x = int(input())
prices = [int(input()) for _ in range(x)]
res = calculate_min_price_and_coupons(m, n, k, x, prices)
for min_price, min_coupons in res:
print(min_price, min_coupons)
const readline = require('readline').createInterface({
input: process.stdin,
output: process.stdout
});
const MAX_PRICE = 10005;
const MAX_COUPONS = 105;
let input = [];
readline.on('line', line => {
input.push(line);
if (input.length === parseInt(input[1]) + 2) {
readline.close();
}
});
readline.on('close', () => {
let [m, n, k] = input[0].split(' ').map(Number);
let x = Number(input[1]);
let prices = input.slice(2).map(Number);
for (let i = 0; i < x; i++) {
let price = prices[i];
let dp = new Array(MAX_PRICE).fill(MAX_COUPONS);
dp[price] = 0;
// Full Reduction and No Threshold coupons
for (let j = price; j >= 10; j--) {
// Using Full Reduction coupons
for (let l = 1; l <= m && l * 100 <= j; l++) {
dp[j - l * 10] = Math.min(dp[j - l * 10], dp[j] + l);
}
// Using No Threshold coupons
if (j >= 5 && k > 0) {
dp[j - 5] = Math.min(dp[j - 5], dp[j] + 1);
}
}
let minPrice = price;
let minCoupons = dp[0];
for (let j = 0; j < price; j++) {
if (dp[j] <= k) {
minPrice = j;
minCoupons = dp[j];
break;
}
}
// Discount coupons
if (n > 0 && price * 0.92 < minPrice) {
minPrice = Math.floor(price * 0.92);
minCoupons += 1;
}
console.log(`${minPrice} ${minCoupons}`);
}
});
package main
import (
"fmt"
)
const (
MAX_PRICE = 10005
MAX_COUPONS = 105
)
func main() {
var m, n, k, x int
fmt.Scan(&m, &n, &k, &x)
prices := make([]int, x)
for i := 0; i < x; i++ {
fmt.Scan(&prices[i])
}
dp := make([]int, MAX_PRICE)
for _, price := range prices {
for i := 0; i <= price; i++ {
dp[i] = MAX_COUPONS
}
dp[price] = 0
// Full Reduction and No Threshold coupons
for j := price; j >= 10; j-- {
// Using Full Reduction coupons
for l := 1; l <= m && l*100 <= j; l++ {
dp[j-l*10] = min(dp[j-l*10], dp[j]+l)
}
// Using No Threshold coupons
if j >= 5 && k > 0 {
dp[j-5] = min(dp[j-5], dp[j]+1)
}
}
minPrice := price
minCoupons := dp[0]
for j := 0; j < price; j++ {
if dp[j] <= k {
minPrice = j
minCoupons = dp[j]
break
}
}
// Discount coupons
if n > 0 && int(float64(price)*0.92) < minPrice {
minPrice = int(float64(price) * 0.92)
minCoupons += 1
}
fmt.Println(minPrice, minCoupons)
}
}
func min(a, b int) int {
if a < b {
return a
}
return b
}