小红的优惠券

[题目链接](https://www.nowcoder.com/practice/8235baca28854e15b68a47a17d817929)

思路

本题是一道简单的模拟/贪心题。

小红有一个订单总额 和 张优惠券，每张优惠券有门槛 和减免 ，表示"满 元减 元"。只能使用一张优惠券，求最少需要支付多少钱。

做法

遍历所有优惠券，对于每张优惠券：

• 如果 ，说明满足使用条件，实际支付为 ；
• 否则该优惠券不可用。

在所有可用优惠券中，选择减免金额 最大的那张即可。当然也可能没有任何优惠券可用，此时答案就是 。

实现上，初始化答案为 ，遍历每张优惠券取 即可。

代码

[sol-C++]

#include <bits/stdc++.h>
using namespace std;
int main(){
    int total, n;
    scanf("%d%d", &total, &n);
    int ans = total;
    for(int i = 0; i < n; i++){
        int x, y;
        scanf("%d%d", &x, &y);
        if(total >= x){
            ans = min(ans, total - y);
        }
    }
    printf("%d\n", ans);
    return 0;
}

[sol-Java]

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int total = sc.nextInt();
        int n = sc.nextInt();
        int ans = total;
        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            if (total >= x) {
                ans = Math.min(ans, total - y);
            }
        }
        System.out.println(ans);
    }
}

[sol-Python3]

total, n = map(int, input().split())
ans = total
for _ in range(n):
    x, y = map(int, input().split())
    if total >= x:
        ans = min(ans, total - y)
print(ans)

[sol-JavaScript]

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

复杂度分析

• 时间复杂度: ，遍历所有优惠券一次。
• 空间复杂度: ，只需常数额外空间（JavaScript 需要 存储输入行）。