记录一下思路和内容吧!
第一次遇见这种题果然不会做。。。
我是战神,最喜欢不会做的题,这次弄懂,下次就ac了
- 这道题和那头牛的问题还是不太一样,但是可以对比记忆。
- 先比较 一维的情况,假如只有时间没有等级限制的话,我们只需要把任务从大到小排个序,再从大到小进行枚举,选出一个比它时间大的任意一个即可,因为每个机器都只能用一次,既然给能这个而且对后面的也没有影响,因此选择就是最优情况。
- 在二维的情况下,这里存在一种很强的性质,就是只要时间第一个比第二个大,那么无论等级差多少所获的利润都不会比第一个大,那么只需要按照时间为第一关键字,等级为第二关键字从大到小排序即可,再从大到小依次枚举每个任务,找到比任务大的所有机器按照等级排序,找到最小的比任务大的等级即可。因为每个机器只会贡献一次,而且选择的都是在机器时间是满足的情况下,等级最小的一个即是最优。