Readme

2604.Minimum-Time-to-Eat-All-Grains

直观上我们就会把grains和hens都排序，那么最优解里，从左往右的hens的顺序，必然对应着从左往右grains互不相交的区间。也就是说对于母鸡a<b，如果对应吃到的谷子x>y，这不可能是最优解。

有了这个发现之后，接下来似乎还是无从下手，那就不妨二分搜值。显然我们会设定一个时间T，看看所有的母鸡能在此时间内把所有谷子都吃完。或者说，是否存在一种谷子区间的分配，能够在T里被各个母鸡吃到。如果可行，那么尝试降低T，否则我们就提高T，最终收敛到最优解。

现在考察这个判定函数。因为每个谷子都要被吃，显然我们就从第0号谷子开始考察：它必然是被第0号母鸡吃掉。假设0号谷子在0号母鸡左边，如果两者离得太远（超过了T），那么整体就返回无解。如果在范围内，那么意味着0号母鸡在移动到0号谷子的过程中遇到的所有谷子都能被吃掉。我们记0号母鸡移动到0号谷子的时间是t，那么母鸡在吃完0号谷子还需要返回再花时间t，此时如果还有剩余T-2t，那么就可以往右走，再多吃一点谷子，注意这一段是单程。由此我们可以确定0号母鸡吃的谷子的总数目，假设是j，那么下一个回合我们就考察第j个谷子和第1号母鸡之间的关系，再考察1号母鸡总共能吃几粒谷子，重复这个逻辑。

但是注意，在上面的0号母鸡策略中，其实还有另一种方案，就是先往右走，再折返，再往左边走t的时间保证吃掉0号谷子。这也是可行的。哪种方案更好呢？取决于0号母鸡往右边开拓的范围哪个更远。假设方案1比方案2更好，意味着

T - t*2 > (T-t) / 2 <=> T > 3*t

也就是说，如果T>3t，我们就选取方案1，否则就选取方案2.

由此我们顺次遍历谷子，将一个区间范围内的谷子归入下一个母鸡，在T的约束下确定这个区间范围。直至看能否把所有的谷子都分配完毕。