第十二届蓝桥杯国赛《巧克力》（java实现）
小蓝很喜欢吃巧克力，他每天都要吃一块巧克力。
一天小蓝到超市想买一些巧克力。超市的货架上有很多种巧克力，每种巧克力有自己的价格、数量和剩余的保质期天数，小蓝只吃没过保质期的巧克力，请问小蓝最少花多少钱能买到让自己吃 xx 天的巧克力。
输入描述输入的第一行包含两个整数 x, nx,n，分别表示需要吃巧克力的天数和巧克力的种类数。
接下来 nn 行描述货架上的巧克力，其中第 ii 行包含三个整数 a_i,b_i,c_iai,bi,ci，表示第 ii 种巧克力的单价为 a_iai，保质期还剩 b_ibi 天（从现在开始的 b_ibi 天可以吃），数量为 c_ici。
输出描述输出一个整数表示小蓝的最小花费。如果不存在让小蓝吃 xx 天的购买方案，输出 −1−1。
输入输出样例示例
输入
10 3
1 6 5
2 7 3
3 10 10
输出
18 样例说明
一种最佳的方案是第 11 种买 55 块，第 22 种买 22 块，第 33 种买 33 块。前 55 天吃第 11 种，第 66、77 天吃第 22 种，第 88 至 1010 天吃第 33 种。
评测用例规模与约定对于 3030% 的评测用例，n, x leq 1000n,x≤1000；
对于所有评测用例，1 leq n, x leq 100000，1 leq a_i, b_i, c_i ≤ 10^91≤n,x≤100000，1≤ai,bi,ci≤109。
运行限制 最大运行时间：1s最大运行内存: 256M解析
这题用贪心做。 每个巧克力可以看作一个类，分别有三个属性，分别为价值、保质期和数量。题目问的是在x天中，怎样分配使得价值最小。它既然要求价值最小那我们就首先考虑价值。所以我们选择吃哪块巧克力时优先选择价值最小的，这是第一个策略。这里还得考虑价值相等该怎么办，那肯定是优先吃掉快过期的呗，都能理解吧。
这题有个很奇妙的点是，我们选择巧克力不用现在吃它，有更好的方案。我们选择在离它过期的最后一天吃它，这样一个好处是可以空出前年的时间可以吃掉保质期短的。比如我现在有3块巧克力，它们保质期都是4，但是我不选择现在吃掉，而是第4天吃掉，如果我第一天就吃掉显然给保质期短的磨灭了很多机会。还有就是我不是有3块嘛，第一块第四天吃掉，那我第二块就应该是第三天吃掉，第三块就应该是第二天吃掉，应该能理解是如何选择哪一天的吧。就优先选最晚的（不过期前提下）那一天。
现在我们知道了该如何选择巧克力（首选价值最小的）和如何选择第几天吃（最晚临近过期那天），就写代码咯。直接告诉你们，用一个数组来保存巧克力，输入完之后要对这个数组排序，排序规则就是优选价值最小的，相等就选保质期最短的。用一个treeset集合来保存剩余天数，因为我们只能一天吃一块嘛，比如有5天，我第三天吃了巧克力，是不是集合里就应该只剩第1，2，4，5天呀，这个思维还是有点跳脱哦，大家好好理解。用treeset是因为它可以自动排序，选择每一块巧克力时我需要拿它的保质期和最小的天数比较，看它是否过期了，而treeset可以进行排序，能让我方便地获取最小的。
这题还有个我不解的地方，就是输入的时间。我直接用
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
都不行，会超时！！非得用InputReader这个模板类。有知道原因的小伙伴可以留言告诉我。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;
import java.util.TreeSet;
class Node{
public int val;
public int l;
public int cnt;
public Node(int val, int l, int cnt) {
this.val = val;
this.l = l;
this.cnt = cnt;
}
}
class MyComparator implements Comparator<Node>{
@Override
public int compare(Node o1, Node o2) {
if (o1.val == o2.val) {
return o1.l - o2.l;
}
return o1.val - o2.val;
}
}
public class Main {
public static TreeSet<Integer> se = new TreeSet<Integer>();
public static Node[] a;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
InputReader in = new InputReader();
int x = in.nextInt(), n = in.nextInt();
a = new Node[n + 1];
for (int i = 1; i <= n; i++) {
a[i] = new Node(in.nextInt(), in.nextInt(), in.nextInt());
}
Arrays.sort(a, 1, n + 1, new MyComparator());
for (int i = 1; i <= x; i++) {
se.add(i);
}
int p = 1;
long res = 0;
while (se.size() != 0 && p <= n) {
while (a[p].cnt != 0 && se.size() != 0 && se.first() <= a[p].l) {
res += a[p].val;
a[p].cnt--;
int it = se.lower(a[p].l + 1);
se.remove(it);
}
p++;
}
System.out.print(se.size() != 0 ? -1 : res);
}
}
class InputReader {
BufferedReader buf;
StringTokenizer tok;
InputReader() {
buf = new BufferedReader(new InputStreamReader(System.in));
}
boolean hasNext() {
while (tok == null || !tok.hasMoreElements()) {
try {
tok = new StringTokenizer(buf.readLine());
} catch (Exception e) {
return false;
}
}
return true;
}
String next() {
if (hasNext()) return tok.nextToken();
return null;
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
double nextDouble() {
return Double.parseDouble(next());
}
}
相关知识
【竞赛获奖】第十二届蓝桥杯全国高校视觉艺术设计赛全国选拔赛获奖名单揭晓 美院学子获得四个奖项
AI：互联网程序设计竞赛之蓝桥杯大赛的简介、奖项设置、大赛内容以及蓝桥杯与ACM(ICPC)的四个维度对比之详细攻略
第十六届蓝桥杯全国软件和信息技术专业人才大赛软件赛校内选拔赛的通知
关于第十六届蓝桥杯大赛的报名及培训通知
计算机学院教师积极参加第十六届蓝桥杯大赛省赛师资培训会
蓝桥杯大赛报名指南
第十六届蓝桥杯大赛报名通知
P8812 [蓝桥杯 2022 国 C] 打折
第八届蓝桥杯全国软件和信息技术专业人才大赛报名指南
艺术与传媒学院“新东方杯” 第十二届大学生职业规划大赛院赛结果公示
网址: 第十二届蓝桥杯国赛《巧克力》（java实现） https://m.huajiangbk.com/newsview688768.html
| 上一篇: 巧克力慕斯蛋糕 |
下一篇: 巧克力五瓣花蛋糕 |
