题目链接

小红的优惠券

题目描述

小红的订单总价为 元。她有 张优惠券，每张都是“满 元减 元”。她只能使用一张优惠券，且使用的前提是订单总价 必须大于或等于门槛 。求她最少需要花多少钱。

解题思路

这是一个简单的最优化问题。我们需要在所有可用的优惠券中，找出能使得最终花费最小的那一张。

算法的思路非常直接：

  1. 初始化：我们首先假设不使用任何优惠券，那么需要支付的金额就是订单原价 。我们可以用一个变量 min_cost 来记录当前已知的最低花费，并将其初始值设为 。

  2. 遍历与决策：接下来，我们遍历小红拥有的全部 张优惠券。对于每一张优惠券（满 减 ）：

    • 检查可用性：我们首先判断这张优惠券是否可用。根据题意，条件是订单总价 必须大于或等于优惠券的使用门槛 ，即 。
    • 计算并更新：如果优惠券可用，我们就计算使用它之后的花费，即 。然后，我们将这个新算出的花费与 min_cost 进行比较，如果新花费更低，就更新 min_cost 的值为这个更低的价格。

  3. 最终结果：在检查完所有 张优惠券后，min_cost 变量中存储的，就是小红所需要支付的最低金额。

这个过程保证了我们考虑了所有可能性（包括不使用任何优惠券），并从中找到了最优解。

代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long n;
    int m;
    cin >> n >> m;

    long long min_cost = n;

    for (int i = 0; i < m; ++i) {
        long long x, y;
        cin >> x >> y;
        if (n >= x) {
            min_cost = min(min_cost, n - y);
        }
    }

    cout << min_cost << endl;

    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        int m = sc.nextInt();

        long minCost = n;

        for (int i = 0; i < m; i++) {
            long x = sc.nextLong();
            long y = sc.nextLong();
            if (n >= x) {
                minCost = Math.min(minCost, n - y);
            }
        }

        System.out.println(minCost);
    }
}

import sys

def solve():
    n, m = map(int, sys.stdin.readline().split())
    
    min_cost = n
    
    for _ in range(m):
        x, y = map(int, sys.stdin.readline().split())
        if n >= x:
            min_cost = min(min_cost, n - y)
            
    print(min_cost)

solve()

算法及复杂度

  • 算法：线性扫描
  • 时间复杂度：，其中 是优惠券的数量。我们只需要遍历一次所有的优惠券。
  • 空间复杂度：。我们只需要常数级别的额外空间来存储最低花费和当前优惠券信息。