网站开发和设计如何合作,网站备案要几天,成都网站改版,苏州seo招聘文章目录 巧克力题目描述解题分析贪心 巧克力
题目描述
小蓝很喜欢吃巧克力#xff0c;他每天都要吃一块巧克力。
一天小蓝到超市想买一些巧克力。超市的货架上有很多种巧克力#xff0c;每种巧克力有自己的价格、数量和剩余的保质期天数#xff0c;小蓝只吃没过保质期的… 文章目录 巧克力题目描述解题分析贪心 巧克力
题目描述
小蓝很喜欢吃巧克力他每天都要吃一块巧克力。
一天小蓝到超市想买一些巧克力。超市的货架上有很多种巧克力每种巧克力有自己的价格、数量和剩余的保质期天数小蓝只吃没过保质期的巧克力请问小蓝最少花多少钱能买到让自己吃 x 天的巧克力。
输入描述
输入的第一行包含两个整数 x, n分别表示需要吃巧克力的天数和巧克力的种类数。
接下来 n 行描述货架上的巧克力其中第 i 行包含三个整数 ai, bi, ci表示第 i 种巧克力的单价为 ai保质期还剩 bi 天从现在开始的 bi 天可以吃数量为 ci。
输出描述
输出一个整数表示小蓝的最小花费。如果不存在让小蓝吃 x 天的购买方案输出ࠪ -1。
输入输出样例 示例 输入 10 3
1 6 5
2 7 3
3 10 10输出 18样例说明 一种最佳的方案是第 1 种买 5 块第 2 种买 2 块第 3 种买 3 块。前 5 天吃第 1 种第 6、7 天吃第 2 种第 8 至 10 天吃第 3 种。
评测用例规模与约定 对于 30% 的评测用例n, x ≤ 1000。 对于所有评测用例1 ≤ n, x ≤ 1000001 ≤ ai, bi, ci ≤ 109。
解题分析
显然要使花费的钱最少我们就要尽量选用价格尽量低的巧克力。
对于一个巧克力设其保质期为b那么我们仅可能在第1~ b天会吃它。而如果第1~ b天每天都已经安排好了要吃的巧克力那该巧克力买了就没有任何意义我们称其为没用的巧克力。
假设我们现在买了一个保质期为b的巧克力那我们就要尽量将该巧克力放在第b天吃。而如果第b天已经有巧克力吃了我们就尽量将其放在b-1天吃
如此我们就能保证可以尽可能多的购买价格尽量低的有用的巧克力。
而对于保质期为b的巧克力要快速确定将其放在哪一天吃 可以维护-一个记录着没有安排巧克力吃的日期的set这样我们只要在set中二分第一个小于b的日期就可以快速确定了。然后再通过以上贪心策略模拟一遍即可。
或者利用队列从最后一天开始考虑把符合要求的巧克力都加入备选集合然后选择价格最便宜的巧克力用优先队列维护即可。
贪心
下面是对您提供的C代码的详细注释。
#includebits/stdc.h // 引入所有标准库
using namespace std;// 定义一个结构体node用来表示巧克力的属性
struct node
{int val,days,cnt; // val: 单价, days: 保质期剩余天数, cnt: 数量
}p[100010]; // 创建一个node数组p用来存储每种巧克力的信息// 自定义比较函数cmp用于排序
bool cmp(node a, node b)
{// 如果价格相同则按照保质期剩余天数从大到小排序if(a.val b.val) return a.days b.days;// 否则按照价格从小到大排序return a.val b.val;
}// 定义一个集合day用来存储x天即小蓝吃巧克力的每一天
setint day;int main()
{int x, n; // x: 需要吃巧克力的天数, n: 巧克力的种类数cin x n; // 读入x和n的值// 循环读入每种巧克力的价格、保质期剩余天数和数量for(int i 1; i n; i)cin p[i].val p[i].days p[i].cnt;// 根据自定义的比较函数cmp对巧克力数组p进行排序sort(p 1, p n 1, cmp);// 初始化集合day存入每一天作为元素for(int i 1; i x; i)day.insert(i);long long sum 0; // sum用来记录总花费int q 1; // q用来遍历每一种巧克力// 当仍有需要吃的天数且还有巧克力未考虑时执行循环while(day.size() ! 0 q n){// 当当前巧克力还有剩余、还有需要吃的天数、// 并且最早的未安排的天数小于等于当前巧克力的保质期时执行循环while(p[q].cnt ! 0 day.size() ! 0 *day.begin() p[q].days){sum p[q].val; // 累加当前巧克力的价格到总花费p[q].cnt--; // 当前巧克力的数量减一// 使用upper_bound找到第一个大于当前巧克力保质期的天数然后往前移动一个位置auto t day.upper_bound(p[q].days);t--;// 从集合day中删除已经安排给当前巧克力的天数day.erase(t);}q; // 考虑下一种巧克力}// 如果day集合不为空说明存在无法满足吃完x天的巧克力的情况输出-1if(day.size() ! 0) cout -1;// 否则输出总花费sumelse cout sum;return 0;
}代码的工作流程如下
读入需要吃巧克力的天数x和巧克力的种类数n。读入每种巧克力的价格、保质期剩余天数和数量存入数组p。根据价格和保质期对巧克力进行排序。初始化一个集合day表示小蓝每天都需要吃巧克力。遍历每种巧克力同时检查集合day中是否有对应的天需要吃巧克力。如果找到匹配的天数就从day中移除该天并从当前种类的巧克力数量中减去一块同时累加其价格到总花费sum中。最后如果day集合为空表明所有天都分配了巧克力输出总花费如果day不为空输出-1表示无法满足小蓝全部天数的巧克力需求。
