魔法师 (@Constanline) 在 Leetcode每日一题 —— 2141. 同时运行 N 台电脑的最长时间 中发帖
2141. 同时运行 N 台电脑的最长时间
思路
看完题没有太好的想法,主要是如何判断什么时候需要换电呢,因为由示例一可见,有时需要把一块电池拆成两段或者多段使用。后来我换了一种思路,不再考虑如何续接,由题意可看出要保证尽量多的可用电池数量,所以我假设每过一分钟,所有的电脑都重新连接电池剩余电量最多的,这样就能保证可用数量一直是最多的而且趋近于平均使用,但是每分钟计算一次的话肯定要超时的。按照这个思路延伸,可以假设容量前n的电池一直充电,容量小的电池在有电池容量不足的时候进行补充,而且这种补充因为有足够的电池数量(前n个不动),所以可以1分1分的统计。这样我们可以把电池电量降序排列(因为Arrays.sort对非包装类型只能升序,所以代码里为了减少耗时我用升序反向处理的),比n多出来的电池都可以算作补充能源,从n开始后往前将多余能源补足前一个的量,直到无法补足为止,如果到了第一个还没用...