P3130. 在规定时间内获得的最大报酬

解题思路

本题的陷阱在于，每一个任务给定的时间 K 是 最晚完成时间，这意味着该任务可以在小于等于 K 的任意一个时刻完成。

示例说明

以示例二为例：

• 在单位时间 1，第 0-4 个任务都是可以选择去完成的任务。
• 在单位时间 2，第 1-4 个任务都是可以选择去完成的任务。
• 在单位时间 3，第 2-4 个任务都是可以选择去完成的任务。

关键结论

如果意识到了这一点，那么以下结论是显而易见的：随着时间增大，某些任务已经错过了其对应的最晚完成时间 K，那么可以选择的任务是变得越来越少的。

难点分析

难点在于，在当前时间较小的时候，如果我们面临多个选择，我们无法确定应该选择哪个任务。因为我们在做选择时存在两个不同的维度需要考虑：

• 该任务的报酬 L 尽可能地大
• 该任务的最晚完成时间 K 尽可能地小

如果正向地考虑时间变化，我们 没有办法同时保持上述两个维度都满足最优的条件。换句话说，没有办法贪心地从局部最优得到全局最优解。

特殊情况与贪心策略

考虑一种特殊情况，假设仅存在一个任务 i 的最晚完成时间 K 大于等于总体最晚完成时间 T，那么在时刻 T 时，只有这一个任务 i 可以被选择。即使这个任务 i 有可能可以在更早完成，我们也希望 把它拖到时刻 T 来完成，这样才能让时刻 T 之前的单位时间去完成其他任务。

以示例三为例，对于时刻 t = 2，仅存在工作 1 的最晚完成时间是 K = 2，那么工作 1 我们一定希望 把它放在 t = 2 来完成而不是放在 t = 1 来完成，因为这样才能在 t = 1 时刻，去完成更多任务。

反向贪心算法

所以贪心策略应该是 从后往前考虑时间变化。即时刻 t 从 T 递减变化到 1。

考虑某一个时刻 t，假设该时刻有 m 个可以选择的任务，那么我们会在里面 挑出报酬最大的那个任务 去完成。

在时刻 t-1，除了剩下的 m-1 个任务，还有最晚完成时间 K = t-1 的若干个任务（假设数量为 p）需要放在一起考虑，那么此时一共有 p+m-1 个任务需要考虑，同样在里面 挑出报酬最大的那个任务 去完成。

其中 dic_task_last_t 为一个哈希表，储存了最晚完成时间为时刻 t 的任务的报酬。其：

• key 为时刻 t
• value 为由最晚完成时间为 t 的任务的报酬所构成的列表

优化建议

注意：上述挑选单个时刻里最大值的过程，更好的方法是用一个 最大容量为 T 的优先队列/堆 来维护，这样单个时刻挑选最大值的复杂度可以降为 O(logT)。但因为数据量很小，所以直接排序也是可以通过的。感兴趣的同学可以尝试用优先队列的方法来维护上述过程。