蓝桥杯国赛每日一题:巧克力(贪心,堆)
蓝桥杯国赛每日一题:巧克力(贪心,堆)

Cocobol0 于 2024-05-29 20:02:06 发布
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
小蓝很喜欢吃巧克力,他每天都要吃一块巧克力。
一天小蓝到超市想买一些巧克力。超市的货架上有很多种巧克力,每种巧克力有自己的价格、数量和剩余的保质期天数,小蓝只吃没过保质期的巧克力,请问小蓝最少花多少钱能买到让自己吃 x 天的巧克力。
输入格式
输入的第一行包含两个整数 x,n,分别表示需要吃巧克力的天数和巧克力的种类数。
接下来 n 行描述货架上的巧克力,其中第 i 行包含三个整数 ai,bi,ci,表示第 i 种巧克力的单价为 ai,保质期还剩 bi 天(从现在开始的 bi 天可以吃),数量为 ci。
输出格式
输出一个整数表示小蓝的最小花费。如果不存在让小蓝吃 x 天的购买方案,输出 −1。
输入输出样例
输入 #1复制
10 3 1 6 5 2 7 3 3 10 10
输出 #1复制
18
说明/提示
【样例说明】
一种最佳的方案是第 1 种买 5 块,第 2 种买 2 块,第 3 种买 3 块。前 5 天吃第 1 种,第 6、7 天吃第 2 种,第 8至 10 天吃第 3 种。
【评测用例规模与约定】
对于 30% 的评测用例 n,x≤1000。
对于所有评测用例,1≤n,x≤10^5,1≤ai,bi,ci≤10^9。
解题思路:由于有些巧克力日期过期后不能再食用,
相关知识
蓝桥杯国赛每日一题:巧克力(贪心,堆)
第十二届蓝桥杯国赛《巧克力》(java实现)
计算机学院教师积极参加第十六届蓝桥杯大赛省赛师资培训会
蓝桥杯大赛报名指南
AI:互联网程序设计竞赛之蓝桥杯大赛的简介、奖项设置、大赛内容以及蓝桥杯与ACM(ICPC)的四个维度对比之详细攻略
“恒为杯”江南大学第三届Python编程竞赛举办
第十六届蓝桥杯大赛报名通知
P8812 [蓝桥杯 2022 国 C] 打折
【竞赛获奖】第十二届蓝桥杯全国高校视觉艺术设计赛全国选拔赛获奖名单揭晓 美院学子获得四个奖项
第十六届蓝桥杯全国软件和信息技术专业人才大赛软件赛校内选拔赛的通知
原文链接: 蓝桥杯国赛每日一题:巧克力(贪心,堆) https://m.huajiangbk.com/newsview1965643.html
| 上一篇: 超市货架的一些摆放技巧和陈列规范... | 下一篇: 红包购物挑战 |



