题解 | #小红的优惠券#

题目链接

小红的优惠券

题目描述

小红的购物车结算金额为 $x$ 元，她手中有 $n$ 张优惠券。第 $i$ 张优惠券的规则为“满 $a_i$ 元立减 $b_i$ 元”。这意味着，只有当 $x \ge a_i$ 时，这张优惠券才能使用，使用后可以减免 $b_i$ 元。

小红最多只能使用一张优惠券。请问，她最少需要支付多少元？

解题思路

这是一个简单的决策问题。小红的目标是最大化优惠金额，从而最小化支付金额。

决策过程如下：

初始状态：如果不使用任何优惠券，小红需要支付 $x$ 元。我们可以将这个金额作为初始的“最小支付金额”。
遍历所有选项：小红需要检查她手中的每一张优惠券，看看哪一张能给她带来最大的优惠。
筛选可用优惠券：对于第 $i$ 张优惠券（满 $a_i$ 减 $b_i$ ），首先要判断它是否可用。可用条件是购物车金额 $x$ 大于或等于该券的门槛 $a_i$ ，即 $x \ge a_i$ 。
寻找最大减免额：在所有可用的优惠券中，小红应该选择那张减免金额 $b_i$ 最大的。因为使用任何一张券都不会有额外成本，所以选择减得最多的券，最终支付的金额自然就最少。
计算最终支付金额：
- 找到所有可用优惠券中最大的减免金额，我们称之为 max_discount。
- 如果没有任何一张优惠券可用，那么 max_discount 就是0。
- 最终需要支付的金额就是 $x - \text{max\_discount}$ 。

算法步骤

读取购物车金额 $x$ 和优惠券数量 $n$ 。
初始化一个变量 max_discount 为 0，用来记录可用的最大减免额。
进入一个循环，执行 $n$ 次，每次读取一张优惠券的门槛 $a$ 和减免额 $b$ 。
在循环中，判断该优惠券是否可用（ $x \ge a$ ）。
如果可用，就将它的减免额 $b$ 与当前的 max_discount 比较，更新 max_discount = max(max_discount, b)。
循环结束后，max_discount 中就保存了最佳的优惠金额。
计算并输出最终结果 $x - \text{max\_discount}$ 。

代码

c++
java
python

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    long long x, n;
    cin >> x >> n;
    
    long long max_discount = 0;
    
    for (int i = 0; i < n; ++i) {
        long long a, b;
        cin >> a >> b;
        
        // 判断优惠券是否可用
        if (x >= a) {
            max_discount = max(max_discount, b);
        }
    }
    
    cout << x - max_discount << endl;
    
    return 0;
}

import java.util.Scanner;
import java.lang.Math;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long x = sc.nextLong();
        int n = sc.nextInt();
        
        long maxDiscount = 0;
        
        for (int i = 0; i < n; i++) {
            long a = sc.nextLong();
            long b = sc.nextLong();
            
            // 判断优惠券是否可用
            if (x >= a) {
                maxDiscount = Math.max(maxDiscount, b);
            }
        }
        
        System.out.println(x - maxDiscount);
    }
}

import sys

def solve():
    x, n = map(int, sys.stdin.readline().split())
    
    max_discount = 0
    
    for _ in range(n):
        a, b = map(int, sys.stdin.readline().split())
        
        # 判断优惠券是否可用
        if x >= a:
            max_discount = max(max_discount, b)
            
    print(x - max_discount)

solve()

算法及复杂度

算法：模拟/贪心
时间复杂度：我们需要遍历所有的 $n$ 张优惠券来找到最佳选择。因此，总时间复杂度为 $\mathcal{O}(n)$ 。
空间复杂度：我们只需要常数个变量来存储购物车金额、最大减免额等信息。因此，空间复杂度为 $\mathcal{O}(1)$ 。