本文涉及的基础知识点
C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频
题目
给你一个下标从 0 开始长度为 n 的整数数组 stations ，其中 stations[i] 表示第 i 座城市的供电站数目。
每个供电站可以在一定 范围 内给所有城市提供电力。换句话说，如果给定的范围是 r ，在城市 i 处的供电站可以给所有满足 |i - j| <= r 且 0 <= i, j <= n - 1 的城市 j 供电。
|x| 表示 x 的 绝对值 。比方说，|7 - 5| = 2 ，|3 - 10| = 7 。
一座城市的 电量 是所有能给它供电的供电站数目。
政府批准了可以额外建造 k 座供电站，你需要决定这些供电站分别应该建在哪里，这些供电站与已经存在的供电站有相同的供电范围。
给你两个整数 r 和 k ，如果以最优策略建造额外的发电站，返回所有城市中，最小供电站数目的最大值是多少。
这 k 座供电站可以建在多个城市。
示例 1：
输入：stations = [1,2,4,5,0], r = 1, k = 2
输出：5
解释：
最优方案之一是把 2 座供电站都建在城市 1 。
每座城市的供电站数目分别为 [1,4,4,5,0] 。
- 城市 0 的供电站数目为 1 + 4 = 5 。
- 城市 1 的供电站数目为 1 + 4 + 4 = 9 。
- 城市 2 的供电站数目为 4 + 4 + 5 = 13 。
- 城市 3 的供电站数目为 5 + 4 = 9 。
- 城市 4 的供电站数目为 5 + 0 = 5 。
供电站数目最少是 5 。
无法得到更优解，所以我们返回 5 。
示例 2：
输入：stations = [4,4,4,4], r = 0, k = 3
输出：4
解释：
无论如何安排，总有一座城市的供电站数目是 4 ，所以最优解是 4 。
参数范围：
n == stations.length
1 <= n <= 105
0 <= stations[i] <= 105
0 <= r <= n - 1
0 <= k <= 109
分析
时间复杂度
O(nlogm)，m= sum(stations)+k。
第一层循环
如果任何城市的最小供电站数大于等于llTarget，则任何城市的最小供电站数一定llTarget-1，如果有多个满足条件的，我们返回最后一个。显然用左闭右开的二分。极限情况下能有多少供电站？所有供电站（已建和可建的)都可以供应所有城市。
第二层循环
当前城市供电站不足的时候，在right城市建立足够的供电站。
变量说明
| i | 当前城市 |
| llTarget | 让所有城市至少有iTarget个供电站 |
| llNeed | 让所有城市至少有iTarget个供电站，需要新建多少个供电站 |
| stations | 各城市供电站（新建、已有）之和 |
| llHas | 能给当前城市供电的供电站，包括处理之前城市而建立的供电站 |
| left | 给当前城市供电的最左城市 |
| right | 能给当前城市供电的最右城市 |
注意
r可以大于stations.size()
代码
核心代码
class Solution { public: long long maxPower(vector<int>& stations, int r, int k) { m_iR = r; m_iK = k; m_stations = stations; long long left = 0, right = std::accumulate(stations.begin(), stations.end(),0LL) + k + 1; //左闭右开 while (right - left > 1) { const long long mid = left + (right - left) / 2; if (TargetNeed(mid)) { left = mid; } else { right = mid; } } return left; } //所有城市供电站达到iTarget，需要新建多少供电站 bool TargetNeed(long long llTarget) { vector<int> stations = m_stations; long long llHas = 0; int left = 0; int right = min(m_iR, (int)stations.size() - 1);//[left,right]表示能够给此城市供电的电站 for (int i = 0; i <= right; i++) { llHas += stations[i]; } long long llNeed = 0; auto Add = [&]() { const long long curNeed = llTarget - llHas; if (curNeed > 0) { llNeed += curNeed; if (llNeed > m_iK) { return false; } stations[right] += curNeed; llHas += curNeed; } return true; }; if (!Add()) { return false; } for (int i = 1; i < stations.size(); i++) { if (i - left > m_iR) { llHas -= stations[left]; left++; } if (right+1 < stations.size()) { right++; llHas += stations[right]; } if (!Add()) { return false; } } return true; } int m_iR; int m_iK; vector<int> m_stations; };
测试用例
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() { Solution slu; vector stations = { 1, 2, 4, 5, 0 }; int r = 0; int k = 0; long long res; stations = { 1, 2, 4, 5, 0 }; r = 1, k = 2; res = slu.maxPower(stations, r, k); Assert(5LL, res); stations = {1 }; r = 0, k = 3; res = slu.maxPower(stations, r, k); Assert(4LL, res); stations = { 0 }; r = 0, k = 0; res = slu.maxPower(stations, r, k); Assert(0LL, res); stations = { 4, 4, 4, 4 }; r = 0, k = 3; res = slu.maxPower(stations, r, k); Assert(4LL, res); stations.assign(2, 1); r = 1; k = 1; res = slu.maxPower(stations, r, k); Assert(3LL, res); stations.assign(100000, 100000); r = 100000; k = 1e9; res = slu.maxPower(stations, r, k); Assert(long long(1e10+1e9+0.5), res); //CConsole::Out(res); }
