作者推荐
本文涉及的基础知识点
题目
你有 n 台电脑。给你整数 n 和一个下标从 0 开始的整数数组 batteries ，其中第 i 个电池可以让一台电脑 运行 batteries[i] 分钟。你想使用这些电池让 全部 n 台电脑 同时 运行。
一开始，你可以给每台电脑连接 至多一个电池 。然后在任意整数时刻，你都可以将一台电脑与它的电池断开连接，并连接另一个电池，你可以进行这个操作 任意次 。新连接的电池可以是一个全新的电池，也可以是别的电脑用过的电池。断开连接和连接新的电池不会花费任何时间。
注意，你不能给电池充电。
请你返回你可以让 n 台电脑同时运行的 最长 分钟数。
示例 1：
输入：n = 2, batteries = [3,3,3]
输出：4
解释：
一开始，将第一台电脑与电池 0 连接，第二台电脑与电池 1 连接。
2 分钟后，将第二台电脑与电池 1 断开连接，并连接电池 2 。注意，电池 0 还可以供电 1 分钟。
在第 3 分钟结尾，你需要将第一台电脑与电池 0 断开连接，然后连接电池 1 。
在第 4 分钟结尾，电池 1 也被耗尽，第一台电脑无法继续运行。
我们最多能同时让两台电脑同时运行 4 分钟，所以我们返回 4 。
示例 2：
输入：n = 2, batteries = [1,1,1,1]
输出：2
解释：
一开始，将第一台电脑与电池 0 连接，第二台电脑与电池 2 连接。
一分钟后，电池 0 和电池 2 同时耗尽，所以你需要将它们断开连接，并将电池 1 和第一台电脑连接，电池 3 和第二台电脑连接。
1 分钟后，电池 1 和电池 3 也耗尽了，所以两台电脑都无法继续运行。
我们最多能让两台电脑同时运行 2 分钟，所以我们返回 2 。
提示：
1 <= n <= batteries.length <= 105
1 <= batteries[i] <= 109
分析
时间复杂度
O(logmlogk) 。两层二分查找。第一层： 枚举可能的时间，log1014，一台电脑，电池数和电池容量都最大。第二层：计算那些电池会浪费,logk。
原理
如果运行时间mid，那么电池容量超过mid的，必定浪费。不超过mid必定不浪费。
每分钟都更换电池，选择电池容量最大的电池。假定某电池，在倒数第t分钟发生了浪费。容量为t，没被选中。那意味：除被浪费的电池外，还有n块电池，剩余容量大于等于t。这些电池总够支撑t分钟。结论：如果发生浪费，那必定可能支撑t分钟。
变量解释
| mValueCount | key是电池容量，value是电池容量为key的数量 |
| mValueToSumMoreCount | key是电池容量,value分别是：电池容量小于等于key的总电池容量，电池容量小于等于key的电池数量 |
代码
核心代码
class Solution { public: long long maxRunTime(int n, vector& batteries) { std::map<int, int> mValueCount; for (const auto& n : batteries) { mValueCount[n]++; } std::map<const long long,std::pair<long long,int>> mValueToSumMoreCount; int iMoreNum = batteries.size(); mValueToSumMoreCount[-1] = make_pair(0, iMoreNum);//避免异常判断 long long llSum = 0; for (const auto& [value, cnt] : mValueCount) { iMoreNum-= cnt; llSum += (long long)value * cnt; mValueToSumMoreCount[value] = make_pair(llSum, iMoreNum); }
//左闭右开空间 long long left = 0, right = 1e14+1; while (right - left > 1) { const auto mid = left + (right - left) / 2; const long long llNeed = mid* n; auto it = std::prev(mValueToSumMoreCount.upper_bound(mid)); const long long llHas = it->second.first + mid* it->second.second; if (llHas >= llNeed) { left = mid; } else { right = mid; } } return left; }
};
测试用例
template void Assert(const vector& v1, const vector& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { assert(v1[i] == v2[i]); } } template void Assert(const T& t1, const T& t2) { assert(t1 == t2); } int main() { int n; vector batteries; long long res; { Solution slu; n = 2, batteries = { 3,3,3 }; auto res = slu.maxRunTime(n, batteries); Assert(4LL, res); } { Solution slu; n = 2, batteries = {1,1,1,1 }; auto res = slu.maxRunTime(n, batteries); Assert(2LL, res); } //CConsole::Out(res);
}
优化
可以排序后，利用数组记录前缀和。两种的索引是有对应关系的。
class Solution { public: long long maxRunTime(int n, vector<int>& batteries) { sort(batteries.begin(), batteries.end()); vector<long long> vPreSum = { 0 }; for (const auto& n : batteries) { vPreSum.emplace_back(n + vPreSum.back()); } //左闭右开空间 long long left = 0, right = 1e14 + 1; while (right - left > 1) { const auto mid = left + (right - left) / 2; const long long llNeed = mid * n; int iCount = std::upper_bound(batteries.begin(), batteries.end(), mid) - batteries.begin(); const long long llHas = vPreSum[iCount] + mid * (batteries.size() - iCount); if (llHas >= llNeed) { left = mid; } else { right = mid; } } return left; } };
2023年3月旧代码
class Solution { public: long long maxRunTime(int n, vector& batteries) { std::sort(batteries.begin(), batteries.end()); vector vSum(1); for (const int& i : batteries) { vSum.push_back(i + vSum.back()); } long long left = 0, right = vSum.back() / n + 1 ; while (right > left + 1) { const auto iMid = left + (right - left) / 2; const int iLessNum = std::lower_bound(batteries.begin(), batteries.end(),iMid) - batteries.begin(); long long llHas = vSum[iLessNum] + (long long)iMid * (batteries.size() - iLessNum); if (llHas / n >= iMid) { left = iMid; } else { right = iMid; } } return left; } };
。也就是我们常说的专业的人做专业的事。 |
|如果程序是一条龙，那算法就是他的是睛|
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境：
VS2022 C++17
