小红的优惠券

思路

这题在说什么？小红要结账了，手里有一堆优惠券，每张券都是"满 X 元减 Y 元"的类型，她最多只能用一张，问最少要付多少钱。

那我们的目标就很明确了：在所有能用的优惠券里，挑减免金额最大的那张用。

什么叫"能用"？就是购物金额 >= 这张券的门槛 X。不满足门槛的券直接跳过。

所以做法就是：遍历所有优惠券，如果当前金额够得着这张券的门槛，就记录一下它的减免金额，取最大值。最后用购物金额减去这个最大减免值就是答案。

如果一张券都用不了呢？那最大减免值就是 0，答案就是原价，完全不用特判。

这就是典型的贪心思路——在所有合法选项中选最优的。

代码

#include <iostream>
using namespace std;
int main() {
    int a, n;
    cin >> a >> n;
    int best = 0;                   // 最大减免金额
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        if (a >= x) {               // 够得着门槛才能用
            best = max(best, y);    // 贪心：取最大减免
        }
    }
    cout << a - best << endl;
    return 0;
}

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int n = sc.nextInt();
        int best = 0;                       // 最大减免金额
        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            if (a >= x) {                   // 够得着门槛才能用
                best = Math.max(best, y);   // 贪心：取最大减免
            }
        }
        System.out.println(a - best);
    }
}

a, n = map(int, input().split())
best = 0
for _ in range(n):
    x, y = map(int, input().split())
    if a >= x:
        best = max(best, y)
print(a - best)

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line));
rl.on('close', () => {
    const [a, n] = lines[0].split(' ').map(Number);
    let best = 0;
    for (let i = 0; i < n; i++) {
        const [x, y] = lines[i + 1].split(' ').map(Number);
        if (a >= x) {
            best = Math.max(best, y);
        }
    }
    console.log(a - best);
});

复杂度分析

  • 时间复杂度: ，遍历一次所有优惠券即可。
  • 空间复杂度: ，只用了几个变量，不需要额外存储。

小结

这题是贪心的入门题，核心就一句话：能用的券里挑减免最多的。遍历一遍取 max 就搞定了，连排序都不需要。写的时候把 best 初始化为 0，这样即使没有任何一张券能用，答案也自然是原价，省了一个特判。