51nod 1163

 

有N个任务,每个任务有一个最晚结束时间以及一个对应的奖励。在结束时间之前完成该任务,就可以获得对应的奖励。完成每一个任务所需的时间都是1个单位时间。有时候完成所有任务是不可能的,因为时间上可能会有冲突,这需要你来取舍。求能够获得的最高奖励。

 

Input

Output

Input示例

Output示例

 

先把任务按照日期从小到大排序,然后用now表示现在已经过了几个单位时间,当我们找到的任务的完成时间大于当前已经过去的时间的时候,这个任务可以被执行但是不一定是最优,我们先把它放到答案里。如果找到的任务的完成时间小于等于已经过去的时间,就把这个任务的价值和答案中的最小值进行比较,如果小于最小值,就用这个价值替换原来的最小值(用完成原来价值最小的任务的时间完成现在的任务),这样最后得到的答案一定是最优的。

还有。。。不开long long见祖宗qwq

 

 

发表评论

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