leetcode2141.同时运行N台电脑的最长时间（周赛，困难）

最长时间（周赛，困难）"/>

leetcode2141.同时运行N台电脑的最长时间（周赛，困难）

解法：二分。
假设可以同时运行x分钟，则
大于等于x的电池最多可以运行x分钟min(x, batteries[i])
小于x的电池最多可以运行batteries[i]分钟min(x, batteries[i])。
将这些求和sums，sums >= n *x就可以同时运行x分钟
由于sums>=n * x，所以小于x的电池个数+大于等于x的电池个数一定大于等于电脑的个数。即：可以同时运行x分钟 的充要条件是：sums>=n * x。
电池的安排：大于等于x的单独负责一个电脑，小于x的随便排一个顺序，一个电脑一个电脑凑够x分钟，横向看必定每个电池不一样，所以可以并行运行。
能同时运行x分钟则一定能同时满足x-1分钟，所以满足二分：
left：n * x<=sums
right：其他
return left;

class Solution {
public:long long maxRunTime(int n, vector<int>& batteries) {long long left = 0;long long right = accumulate(batteries.begin(), batteries.end(), 0LL) / n + 1; //while (left + 1 < right) {long long mid = left + (right - left) / 2; //long long sums = 0;for (auto& each : batteries) {sums += min((long long)each, mid);}if (n * mid <= sums) left = mid;else right = mid;}return left;}
};

代码的难点

1：看到取值范围，极限情况下，n=1，length=5次方，b[i]均等于9次方，此时ans为10的14次方，所以：left right mid均为long long类型。
2：left right的取值：
ans最小取1：n 为1，b[i]等于1，length=1。
ans最大取：14次方/accumulate(batteries.begin(), batteries.end(), 0LL) / n。
所以left = 0，right = 1e14+1 或者 accumulate(batteries.begin(), batteries.end(), 0LL) / n + 1。
后者二分查找范围小，效率更高！！！