2021牛客暑期多校训练营6 F.Hamburger Steak

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

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