首页 > 试题广场 >

小红的优惠券

[编程题]小红的优惠券
  • 热度指数：4354 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}小红的购物车结算金额为 n 元，她手中有 m 张优惠券。第 j 张优惠券的规则为“满 a_j 元立减 b_j 元”，即若 n\geqq a_j，则使用该券后需支付 n-b_j 元。

\hspace{15pt}小红至多使用一张优惠券，请问最少需要支付多少元？

输入描述:
\hspace{15pt}第一行输入两个整数 n,m\left(1\leqq n\leqq 10^5;\ 1\leqq m\leqq 100\right)。
\hspace{15pt}接下来 m 行，第 j 行输入两个整数 a_j,b_j\left(1\leqq b_j\leqq a_j\leqq 10^5\right)，描述第 j 张优惠券。


输出描述:
\hspace{15pt}输出一个整数，表示小红使用最优策略后需支付的最少金额。
示例1

输入

100 3
300 50
200 30
50 5

输出

95

说明

仅第三张券可用，支付 100-5=95 元。
算法知识视频讲解
添加回答
C
卢小哥头像 卢小哥
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct{
    int limit_price;
    int discount;
}pot_t;
typedef struct{
    pot_t data;
    struct plist *next;
}plist;
int calc_min_price(plist *current, int n)
{
    static int min = -1;
    if(min == -1) min = n;
    int pay = 0;
    if(current->data.limit_price <= n){
        pay = n - current->data.discount;
        if(pay < min)
            min = pay;
    }
    return min;
}
int main() {
    int n,m;
    int min, pay;
    scanf("%d %d",&n,&m);
    plist p; p.next = NULL;p.data.limit_price=0,p.data.discount=0;
    for(int i = 0; i< m;i++){
        plist *pt = (plist *)malloc(sizeof(plist));
        if(pt!=NULL){
            scanf("%d %d",&pt->data.limit_price,&pt->data.discount);
            pt->next = NULL;
        }
        plist *current = &p;
        while(current->next != NULL){
            current= (plist *)current->next;
        }
        current->next = (struct plist *)pt;
    }
    plist *current = (plist *)p.next;
    min = n;
    while(current->next!=NULL){
        min = calc_min_price(current, n);
        current=(plist *)current->next;
    }
    min = calc_min_price(current, n);
    printf("%d",min);
    return 0;
}
发表于 2025-12-04 02:24:44 回复(0)
提交观点

问题信息

贪心
难度：
1条回答 377浏览

热门推荐

相关试题

小红的优惠券

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号