题目链接

小红购物

题目描述

小红准备买 件物品，第 件物品的价格是 。另外，小红有 种优惠券，第 个优惠券是：买一件价格不小于 的商品时，可以减去 的价格。

  • 每件商品最多只能用一次优惠券
  • 每种优惠券可以用多次

小红想知道，自己买全部商品最少需要花多少钱？

输入:

  • 第一行输入两个正整数 ，代表商品数量和优惠券的种类数
  • 第二行输入 个正整数，代表每件商品的价格
  • 接下来的 行，每行输入两个正整数 ，代表第 种优惠券的信息

输出:

  • 一个正整数，代表最终需要花的最少钱数

解题思路

这是一个贪心算法问题，可以通过以下步骤解决：

  1. 对于每件商品，我们需要决定：

    • 是否使用优惠券
    • 如果使用，使用哪种优惠券最划算

  2. 贪心策略：

    • 对于每件商品，尝试所有可用的优惠券（价格不小于 ）
    • 选择使用后价格最低的方案
    • 如果所有优惠券使用后的价格都比原价高，则不使用优惠券

  3. 具体步骤：

    • 遍历每件商品
    • 对每件商品遍历所有优惠券
    • 记录使用优惠券后的最低价格
    • 累加所有商品的最终价格

代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> prices(n);
    for(int i = 0; i < n; i++) {
        cin >> prices[i];
    }
    
    vector<pair<int,int>> coupons(m);
    for(int i = 0; i < m; i++) {
        cin >> coupons[i].first >> coupons[i].second;
    }
    
    long long total = 0;
    for(int price : prices) {
        int minPrice = price;
        for(auto [x, y] : coupons) {
            if(price >= x) {
                minPrice = min(minPrice, price - y);
            }
        }
        total += minPrice;
    }
    
    cout << total << endl;
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        
        int[] prices = new int[n];
        for(int i = 0; i < n; i++) {
            prices[i] = sc.nextInt();
        }
        
        int[] x = new int[m];
        int[] y = new int[m];
        for(int i = 0; i < m; i++) {
            x[i] = sc.nextInt();
            y[i] = sc.nextInt();
        }
        
        long total = 0;
        for(int price : prices) {
            int minPrice = price;
            for(int j = 0; j < m; j++) {
                if(price >= x[j]) {
                    minPrice = Math.min(minPrice, price - y[j]);
                }
            }
            total += minPrice;
        }
        
        System.out.println(total);
    }
}

n, m = map(int, input().split())
prices = list(map(int, input().split()))
coupons = []
for _ in range(m):
    x, y = map(int, input().split())
    coupons.append((x, y))

total = 0
for price in prices:
    min_price = price
    for x, y in coupons:
        if price >= x:
            min_price = min(min_price, price - y)
    total += min_price

print(total)

算法及复杂度

  • 算法：贪心算法
  • 时间复杂度： - 其中 是商品数量， 是优惠券种类数
  • 空间复杂度： - 需要存储商品价格和优惠券信息