【C++贪心】P8769 [蓝桥杯 2021 国 C] 巧克力|普及+
![【C++贪心】P8769 [蓝桥杯 2021 国 C] 巧克力|普及+](https://qiniu.meowparty.cn/coder.2023/2026-03-24/cover_1774297204365_f9fa20f60ff6477ca9ae2a9f90afc408.png)
本文涉及知识点
[蓝桥杯 2021 国 C] 巧克力
题目描述
小蓝很喜欢吃巧克力，他每天都要吃一块巧克力。
一天小蓝到超市想买一些巧克力。超市的货架上有很多种巧克力，每种巧克力有自己的价格、数量和剩余的保质期天数，小蓝只吃没过保质期的巧克力，请问小蓝最少花多少钱能买到让自己吃 x x x 天的巧克力。
输入格式
输入的第一行包含两个整数 x x x， n n n，分别表示需要吃巧克力的天数和巧克力的种类数。
接下来 n n n 行描述货架上的巧克力，其中第 i i i 行包含三个整数 a i a_i ai， b i b_i bi， c i c_i ci，表示第 i i i 种巧克力的单价为 a i a_i ai，保质期还剩 b i b_i bi 天（从现在开始的 b i b_i bi 天可以吃），数量为 c i c_i ci。
输出格式
输出一个整数表示小蓝的最小花费。如果不存在让小蓝吃 x x x 天的购买方案，输出 − 1 −1 −1。
样例 #1
样例输入 #1
10 3 1 6 5 2 7 3 3 10 10 样例输出 #1
18 提示
【样例说明】
一种最佳的方案是第 1 1 1 种买 5 5 5 块，第 2 2 2 种买 2 2 2 块，第 3 3 3 种买 3 3 3 块。前 5 5 5 天吃第 1 1 1 种，第 6 6 6、 7 7 7 天吃第 2 2 2 种，第 8 8 8 至 10 10 10 天吃第 3 3 3 种。
【评测用例规模与约定】
对于 30 % 30\% 30% 的评测用例， n , x ≤ 1000 n,x \le 1000 n,x≤1000。
对于所有评测用例， 1 ≤ n , x ≤ 1 0 5 1\le n,x\le 10^5 1≤n,x≤105， 1 ≤ a i , b i , c i ≤ 1 0 9 1 ≤ a_i,b_i ,c_i\le10^9 1≤ai,bi,ci≤109。
蓝桥杯 2021 国赛 C 组 I 题。
贪心
如果价格低的和价格高的，竞争同一天。淘汰价格高的。如果两个都能保留或都不能保留，结果一样。如果保留一个，显然保留价格低的合适。
按价格排序。
有序映射记录需要巧克了的天数。初始：1到x。
依次枚举各巧克力。
如果剩余数量为0，处理其它巧克力。
如果s中存在小于等于保质期的数字。将此巧克力分配一块到保质期内最后一天。如果没有，处理下一个巧克力。
如果最终s非空，返回-1。否则返回分配的巧克力之和。
2025年11月19
第x天吃一块保质期x的巧克力。
第x-1天吃保质期 ≥ x − 1 \ge x-1 ≥x−1的巧克力
⋮ \vdots ⋮
第1天吃保质期 ≥ 1 \ge 1 ≥1的巧克力。
第i天小根堆记录保质期 ≥ i \ge i ≥i的巧克力的价格和数量。
代码
核心代码
#include<iostream>#include<sstream>#include<vector>#include<map>#include<unordered_map>#include<set>#include<unordered_set>#include<string>#include<algorithm>#include<functional>#include<queue>#include<stack>#include<iomanip>#include<numeric>#include<math.h>#include<climits>#include<assert.h>#include<bitset>usingnamespace std;template<classT=int> vector<T>Read(int n,constchar* pFormat ="%d"){ vector<T> ret; T d ;while(n--){scanf(pFormat,&d); ret.emplace_back(d);}return ret;}template<classT=int> vector<T>Read(constchar* pFormat ="%d"){int n;scanf("%d",&n); vector<T> ret; T d;while(n--){scanf(pFormat,&d); ret.emplace_back(d);}return ret;} string ReadChar(int n){ string str;char ch;while(n--){do{scanf("%c",&ch);}while(('\n'== ch)); str += ch;}return str;}classSolution{public:longlongDo(int x, vector<int>& a, vector<int>& b, vector<int>& c){constint N = a.size(); vector<int>inxs(N);iota(inxs.begin(), inxs.end(),0);sort(inxs.begin(), inxs.end(),[&](int i1,int i2){return a[i1]< a[i2];}); set<int> need;for(int i =1; i <= x; i++){ need.emplace(i);}longlong ans =0;for(int i : inxs){for(int cnt =0; cnt < c[i]; cnt++){auto it = need.upper_bound(b[i]);if(need.begin()== it){break;}--it; need.erase(it); ans += a[i];if(need.empty()){return ans;}}}return-1;}};intmain(){#ifdef_DEBUGfreopen("a.in","r",stdin);#endif// DEBUGint x,n;scanf("%d%d",&x,&n); vector<int> a, b, c;int t1, t2, t3;for(int i =0; i < n; i++){scanf("%d%d%d",&t1,&t2,&t3); a.emplace_back(t1); b.emplace_back(t2); c.emplace_back(t3);}auto res =Solution().Do(x,a, b, c); cout << res << std::endl;return0;}单元测试
int x; vector<int> a, b, c;TEST_METHOD(TestMethod11){ x =10, a ={1,2,3}, b ={6,7,10}, c ={5,3,10};auto res =Solution().Do(x, a, b, c);AssertEx(18LL, res);}TEST_METHOD(TestMethod12){ x =10, a ={1}, b ={100}, c ={9};auto res =Solution().Do(x, a, b, c);AssertEx(-1LL, res);}TEST_METHOD(TestMethod13){ x =10, a ={1}, b ={9}, c ={10};auto res =Solution().Do(x, a, b, c);AssertEx(-1LL, res);}扩展阅读
| 我想对大家说的话 |
|---|
| 工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。 |
| 学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作 |
| 有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注 |
| 闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
| 失败+反思=成功 成功+反思=成功 |
视频课程
先学简单的课程，请移步ZEEKLOG学院，听白银讲师（也就是鄙人）的讲解。
https://edu.ZEEKLOG.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.ZEEKLOG.net/lecturer/6176
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。