第十二届蓝桥杯国赛《巧克力》（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{

	@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 se = new TreeSet();
	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) {//剩余天数和剩余巧克力数的判断
			//se.first() <= a[p].l这个意思是现在这种巧克力保质期大于我剩余天中最小的，那肯定就是过期了
			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());
    }
}