小红的购物车优惠券问题题解

一、问题描述

1. 题目内容

小红的购物车结算金额为 ( n ) 元，她手中有 ( m ) 张优惠券。第 ( j ) 张优惠券的规则为“满 ( a_j ) 元立减 ( b_j ) 元”，即若 ( n >= a_j )，则使用该券后需支付 ( n - b_j ) 元。小红至多使用一张优惠券，请问最少需要支付多少元？

2. 输入输出要求

输入：第一行输入两个整数 ( n ) 和 ( m )，分别表示结算金额和优惠券数量。接下来 ( m ) 行，每行输入两个整数 ( a_j ) 和 ( b_j )，表示第 ( j ) 张优惠券的满减条件和立减金额。
输出：输出使用优惠券后最少需要支付的金额。

3. 示例

输入：
输出：80（选择满90减20的优惠券，支付100-20=80元）

二、贪心算法求解思路

1. 贪心策略的核心思想

贪心算法的核心是在每一步选择中都采取当前状态下的最优选择，从而希望导致全局最优解。对于本题，我们需要选择一张优惠券，使得支付金额最小，即 ( n - b_j ) 最小，等价于选择 ( b_j ) 最大的符合条件的优惠券。

2. 贪心选择性质的证明

问题分析：支付金额的最小值由两部分决定：是否使用优惠券，以及使用哪一张优惠券。
贪心选择：若存在符合条件的优惠券（即 ( a_j <= n )），则选择立减金额 ( b_j ) 最大的优惠券，此时支付金额 ( n - b_j ) 最小。
正确性证明：假设存在两张符合条件的优惠券 ( A )（( b_A = 20 )）和 ( B )（( b_B = 10 )），若选择 ( B ) 而非 ( A )，则支付金额为 ( n - 10 )，大于选择 ( A ) 的 ( n - 20 )。因此，选择立减金额最大的优惠券是局部最优选择，且该选择能直接导致全局最优解。

三、算法步骤

输入处理：读取结算金额 ( n ) 和优惠券数量 ( m )。
筛选符合条件的优惠券：遍历所有优惠券，仅保留满减条件 ( a_j <= n ) 的优惠券（因为不满条件无法使用）。
贪心排序：对筛选后的优惠券按立减金额 ( b_j ) 从大到小排序，优先选择立减金额最大的优惠券。
选择最优解：若存在符合条件的优惠券，则使用排序后的第一张（立减金额最大），支付金额为 ( n - b_j )。若不存在符合条件的优惠券，则不使用优惠券，支付金额为 ( n )。

四、代码实现与解析

1. 完整代码

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

struct Coupon {
    int standard;  // 满减条件 a_j
    int money;     // 立减金额 b_j
    Coupon(int standard, int money) : standard(standard), money(money) {}
};

// 比较函数：按立减金额从大到小排序
bool comp(Coupon *a, Coupon *b) {
    return a->money > b->money;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<Coupon *> coupons;

    for (int i = 0; i < m; i++) {
        int standard, money;
        cin >> standard >> money;
        if (standard > n) {
            continue;  // 跳过不符合条件的优惠券
        }
        coupons.push_back(new Coupon(standard, money));
    }

    // 按立减金额从大到小排序
    sort(coupons.begin(), coupons.end(), comp);

    if (coupons.empty()) {
        cout << n;  // 无可用优惠券，直接支付n元
    } else {
        cout << n - coupons[0]->money;  // 使用立减最多的优惠券
    }

    // 释放动态分配的内存（可选，程序结束时系统会自动回收）
    for (auto coupon : coupons) {
        delete coupon;
    }
    return 0;
}

2. 代码解析

结构体 Coupon：存储每张优惠券的满减条件 standard 和立减金额 money。
比较函数 comp：用于排序，确保优惠券按立减金额从大到小排列。
筛选逻辑：通过 if (standard > n) continue; 跳过不符合条件的优惠券，减少后续排序的规模。
排序操作：使用 sort 函数对符合条件的优惠券排序，时间复杂度为 ( O(m \log m) )（( m ) 为优惠券总数）。
结果计算：若有可用优惠券，选择排序后的第一张（立减最多）；否则直接输出原金额。

五、复杂度分析

1. 时间复杂度

输入处理：( O(m) )（遍历 ( m ) 张优惠券）。
排序：( O(k log k) )（( k ) 为符合条件的优惠券数量，( k <= m )），最坏情况下 ( k = m )，时间复杂度为 ( O(m log m) )。
结果计算：( O(1) )。

总时间复杂度：( O(m log m) )，主要由排序操作决定。

2. 空间复杂度

存储优惠券：( O(k) )（( k ) 为符合条件的优惠券数量），最坏情况下 ( O(m) )。
其他变量：( O(1) )。

总空间复杂度：( O(m) )。

六、贪心算法的适用条件

本题能使用贪心算法求解，是因为满足以下条件：

贪心选择性质：局部最优选择（选择立减最多的优惠券）能导致全局最优解。
最优子结构：问题的最优解包含其子问题的最优解（若使用优惠券，则最优解是原问题的最优解；若不使用，则最优解是原金额）。

七、总结

本题通过贪心算法高效求解了购物车优惠券的最优使用问题。核心思路是筛选符合条件的优惠券，按立减金额排序，选择最大立减金额，从而得到最小支付金额。该算法时间复杂度为 ( O(m \log m) )，空间复杂度为 ( O(m) )，能高效处理大规模输入。

贪心算法的关键在于证明贪心选择的正确性，本题通过分析立减金额与支付金额的关系，直观证明了选择最大立减金额的合理性。这种思路可推广到类似的“选择最大收益”或“最小成本”问题中。

题解 | 小红的优惠券