谨以本文纪念我两小时的青春,如有错误请指出~

Description

个汉堡, 个锅,汉堡制作耗时 ,允许拆分时间,由 制作得到。

Solution

  • 首先思考最终需要多少时间?

思维误区:Max足够大时,需要 时间

1 2
100
ans: 100
//虽然有两个锅,但是不能拆成[0, 50] 和 [0, 50],因为一个汉堡不能同时在两个锅上制作

正确的所需时间为

  • 构造方案

按时间排序,从大往小构造,对于当前段,能塞进去就塞进去,不能塞进去的话就把后半部分塞进去,最后记得排序即可。

正确性证明

假设现在有两端长度分别为,满足 ,如果 能够放到 里面,且放 时会超出 ,可以将 分离成两端,如下图所示:

得出必然会满足条件 ,所以我们构造的时间戳是合法的(不会出现[1, 3] [2, 5] 的不合法情况),所以这样构造可以得到正确的结果。

Code

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48394388