[codeforces913D] Too Easy Problems

题目链接

codeforces913D

题解

大概意思就是告诉你有n道题,总时间限制是\(T\),每道题有一个时间消耗\(t[i]\),和限制条件\(k[i]\),如果做的题数大于了\(k\),就不能做这道题,问在\(T\)时间限制内最大的的有效做题数.

又一道背包?不存在的

和C题一样,T太大,不支持背包的空间.

所以我们需要考虑一下怎么样贪心.

可以看出,如果\(k\)越小,那么可以做的题就越多,可选项就越多.

如果\(k\)唯一确定,那么就是在所有的\(k[i]>k\)的几个问题中寻找答案.

如果\(k\)可以减小的话,我们就可以用消耗时间更小的来更新消耗时间更大的题目

运用一个大根堆来维护即可.

所以我们需要排序一下\(k\),维护一个大根堆即可.

  • 如果\(k>siz\),直接输出堆中的元素即可
  • 如果还可以加题就加喽
  • 如果可以替换堆顶元素的话就尽可能替换

一个暴力的贪心.

最后按照题目需要输出

第一行输出一个最多可以解决的题的数量,第二行输出一个k表示你需要解决的题目.

所以我就理解为这两个不是一样的么……

似乎codeforces还写了spjMD不早说让我对着第一个样例调了半天发现有SPJ……

我们统计一个答案,维护一个最大值就好啦~


By:Wahacer

2018.1.9

17:46

发表评论

电子邮件地址不会被公开。 必填项已用*标注