作者推薦
【動態規劃】【廣度優先】LeetCode2258:逃離火災
本文涉及的基礎知識點
二分查找算法合集
滑動窗口
題目
給你一個下標從 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
分析
時間復雜度😮(logmn)，其中m是可能的最大的最小電量std::accumulate(stations.begin(), stations.end(),0LL) + k
二分查找
判斷所有城市的電量能否達到mid，mid為0的時候一定可以，隨著mid增加變得不可能。求最后一個可能的mid，顯然左閉右開的二分。
Can函數
| llSum | 記錄當前城市的最大電量 |
| k | 還可以建造的電站數量 |
| stations | 記錄各城市的電站數，包括新建的 |
如果當前城市電量不夠，則建設電站到本城市電量更好滿足要求。如果無法建造則失敗。選擇能給本城市供電的城市中最右的城市建造電站。
代碼
核心代碼
class Solution {
public:long long maxPower(vector<int>& stations, int r, int k) {m_c = stations.size();long left = 0, right = std::accumulate(stations.begin(), stations.end(),0LL) + k + 1;while (right - left > 1){const auto mid = left + (right - left) / 2;if (Can(stations, mid, r, k)){left = mid;}else{right = mid;}}return left;}bool Can(vector<int> stations, const long long llMin, const int r,int k){long long llSum = 0;for (int i = 0; i < r; i++){//stations[r]下面循環加llSum += stations[i];}for (int i = 0; i < stations.size(); i++){const int iDel = i - r - 1;if (iDel >= 0){llSum -= stations[iDel];}const int iAdd = i + r;if (iAdd < m_c){llSum += stations[iAdd];}if (llSum < llMin){const long long llNeed = llMin - llSum;if (k < llNeed){return false;}k-= llNeed;llSum = llMin;stations[min(iAdd, m_c - 1)] += llNeed;}}return true;}int m_c;
};
測試用例
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{if (v1.size() != v2.size()){assert(false);return;}for (int i = 0; i < v1.size(); i++){assert(v1[i] == v2[i]);}
}template<class T>
void Assert(const T& t1, const T& t2)
{assert(t1 == t2);
}int main()
{vector<int> stations;int r, k;{Solution slu;stations = { 1, 2, 4, 5, 0 };r = 1, k = 2;auto res = slu.maxPower(stations, r, k);Assert(5LL, res);}{Solution slu;stations = { 4,4,4,4 };r = 0, k = 3;auto res = slu.maxPower(stations, r, k);Assert(4LL, res);}//CConsole::Out(res);
}
擴展閱讀
視頻課程
有效學習：明確的目標 及時的反饋 拉伸區（難度合適），可以先學簡單的課程，請移步CSDN學院，聽白銀講師（也就是鄙人）的講解。
https://edu.csdn.net/course/detail/38771
如何你想快
速形成戰斗了，為老板分憂，請學習C#入職培訓、C++入職培訓等課程
https://edu.csdn.net/lecturer/6176
相關下載
想高屋建瓴的學習算法，請下載《喜缺全書算法冊》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 我想對大家說的話 |
|---|
| 聞缺陷則喜是一個美好的愿望，早發現問題，早修改問題，給老板節約錢。 |
| 子墨子言之：事無終始，無務多業 |
。也就是我們常說的專業的人做專業的事。 |
|如果程序是一條龍，那算法就是他的是睛|
測試環境
操作系統：win7 開發環境： VS2019 C++17
或者 操作系統：win10 開發環境： VS2022 C++17
如無特殊說明，本算法用**C++**實現。
)
