力扣5983——同时运行 N 台电脑的最长时间（二分答案，贪心）

思路1、二分答案

答案存在上下界，在限界内二分；
下界定为0，上界按数据量定为1e15；
对于选中的mid值，按这个使用长度给电脑们使用，如果不够n台电脑用，说明mid取大了，r = mid；否则说明mid取小了，l = mid + 1；

难点在于对于选中的使用时长mid，怎么制定使用规则，也就是怎么写check函数；

对于时长高于mid的电池，在整个mid时间中只能给一台电脑供电，其有效时长为mid，对于小于mid的电池，因为可以混合使用，其能发挥全部作用，有效时长为全部；

累加mid条件下的所有有效时长，判断够不够n台电脑用mid时长。

二分结束时就是答案。

代码

另外上界也可以定为sum/n ， 因为最理想的情况下没有浪费，所有电脑都能完全用电，但其实因为有求sum的耗时，并不能节约多少时间

可以将上面代码中上下界这样改更精确

思路2、贪心

在思路1的基础上，其实可以直接从上界往下逼近答案。

假设答案存在，并不断逼近它
首先答案的上界是$\genfrac{}{}{0ex}{}{sum}{n}$，实现最大效率使用；
但为什么答案不是这样最优的情况呢，也就是为什么会有浪费呢？
因为在后面的某一时刻，剩余的电池不足以供所有电脑使用，这时就终止了，多的这些就浪费了，而此时运行的时间就是答案。

逆向思维一下，这些剩余电池其实多出的部分并没有用处，无论多1还是多100，对于总体是没有带来好处的，有点类似木桶效应。

假设ans存在且已知，那么将所有大于ans的电池和电脑配对上并移出考虑范畴，那么剩下的就是最大效率使用电池且不造成浪费的情况，这种情况下可以操作任意次，运行时间就是电脑们平分时间，也就是答案；

在实现上，先对电池排序，ans事先不知道，但知道上界为$\genfrac{}{}{0ex}{}{sum}{n}$，每次将大于的电池移除并更新sum为减去该电池，n为减去该电脑，分子sum减的速度是快于分母n的（因为排过序先处理大电池），所以上界$\genfrac{}{}{0ex}{}{sum}{n}$会不断减少并逼近ans并最终取得。

代码

本文由 在线网速测试 整理编辑，转载请注明出处。