【C++贪心】P8769 [蓝桥杯 2021 国 C] 巧克力|普及+

本文涉及知识点

C++贪心

[蓝桥杯 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++**实现。