🍑 算法题解专栏

🍑 蓝桥 巧克力

10 3
1 6 5
2 7 3
3 10 10

18

🍑 思路

🍤 前边日期安排后影响后边的安排，但后边的安排不会影响前边的安排
🍤 从后往前步步贪心实现局部最优：在可选的范围内选择最便宜的巧克力
🐷 也许是因为后边的限制条件比较多，所以从后面的日期开始安排巧克力

🍑 AC code

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;public class Main
{static class Node{int a;int b;int c;public Node(int a, int b, int c){super();this.a = a;this.b = b;this.c = c;}}public static void main(String[] args){Scanner sc = new Scanner(System.in);int x = sc.nextInt();int n = sc.nextInt();Node[] w = new Node[n];for (int i = 0; i < n; i++){int a = sc.nextInt();// 单价int b = sc.nextInt();// 保质期int c = sc.nextInt();// 数量w[i] = new Node(a, b, c);}
//		按照保质期降序进行排序Arrays.sort(w, (o1, o2) -> o2.b - o1.b);//		按照价格排升序（小根堆）PriorityQueue<Node> heap = new PriorityQueue<>((o1, o2) -> o1.a - o2.a);
//		从后向前每天吃一块巧克力（在允许选择的巧克力中选择最便宜的）int idx = 0;// 记录已进堆的巧克力个数long ans = 0;// 记录总消费while (x-- > 0){while (idx < n && w[idx].b > x)heap.add(w[idx++]);if (heap.size() == 0){ans = -1;break;}Node t = heap.poll();ans += t.a;t.c--;if (t.c != 0)// 重新进堆heap.add(t);}System.out.println(ans);}
}