安排工作以达到最大收益

记住「按难度排序工作、按能力排序工人;指针不回退地纳入难度够到的工作、维护最大收益 best,每个工人取 best」,下面每帧都在套它。

先排序。工作按难度排好:难度 [2, 4, 6, 8, 10]、对应收益 [10, 20, 30, 40, 50](右边面板就是这张「难度→收益」对照表);工人按能力排好 [4, 5, 6, 7]。排序是双指针不回退的前提。

来了个能力 4 的工人。他能做难度不超过 4 的任意工作,目标是从这些工作里挑收益最高的。指针从上一个工人停下的位置接着往右扫,不回退。

难度 2 不超过 4,这份工作他做得了,纳入候选。它的收益是 10,比之前的 best 高,best 更新成 10。注意 best 只增不减,后面工人能力更强、能用的工作只多不少。

难度 4 不超过 4,这份工作他做得了,纳入候选。它的收益是 20,比之前的 best 高,best 更新成 20。注意 best 只增不减,后面工人能力更强、能用的工作只多不少。

再往右,难度 6 已经大于 4,这个工人做不了,停。指针就停在这里,等下一个能力更强的工人接着往右走。

这个工人就拿他能力内的最高收益 20,加进总收益,现在 ans = 20。他不一定做难度最高那份,而是做收益最高那份,这正是要维护 best 的原因。

来了个能力 5 的工人。他能做难度不超过 5 的任意工作,目标是从这些工作里挑收益最高的。指针从上一个工人停下的位置接着往右扫,不回退。

再往右,难度 6 已经大于 5,这个工人做不了,停。指针就停在这里,等下一个能力更强的工人接着往右走。

这个工人就拿他能力内的最高收益 20,加进总收益,现在 ans = 40。他不一定做难度最高那份,而是做收益最高那份,这正是要维护 best 的原因。

来了个能力 6 的工人。他能做难度不超过 6 的任意工作,目标是从这些工作里挑收益最高的。指针从上一个工人停下的位置接着往右扫,不回退。

难度 6 不超过 6,这份工作他做得了,纳入候选。它的收益是 30,比之前的 best 高,best 更新成 30。注意 best 只增不减,后面工人能力更强、能用的工作只多不少。

再往右,难度 8 已经大于 6,这个工人做不了,停。指针就停在这里,等下一个能力更强的工人接着往右走。

这个工人就拿他能力内的最高收益 30,加进总收益,现在 ans = 70。他不一定做难度最高那份,而是做收益最高那份,这正是要维护 best 的原因。

来了个能力 7 的工人。他能做难度不超过 7 的任意工作,目标是从这些工作里挑收益最高的。指针从上一个工人停下的位置接着往右扫,不回退。

再往右,难度 8 已经大于 7,这个工人做不了,停。指针就停在这里,等下一个能力更强的工人接着往右走。

这个工人就拿他能力内的最高收益 30,加进总收益,现在 ans = 100。他不一定做难度最高那份,而是做收益最高那份,这正是要维护 best 的原因。

边界:够不到任何工作贡献 0、能力够全部则取最高收益、无工作返回 0。

认出「双序列排序 + 双指针贪心」母题,best 单调是线性的关键。