作者推荐

【动态规划】【广度优先】2258:逃离火灾

本文涉及的基础知识点

二分查找算法合集
C++算法：滑动窗口总结

2528题

给你一个下标从 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 <= 10⁵
  0 <= stations[i] <= 10⁵
  0 <= r <= n - 1
  0 <= k <= 10⁹

分析

时间复杂度?(logmn)，其中m是可能的最大的最小电量std::accumulate(stations.begin(), stations.end(),0LL) + k

二分查找

判断所有城市的电量能否达到mid，mid为0的时候一定可以，随着mid增加变得不可能。求最后一个可能的mid，显然左闭右开的二分。

Can函数

如果当前城市电量不够，则建设电站到本城市电量更好满足要求。如果无法建造则失败。选择能给本城市供电的城市中最右的城市建造电站。

代码

核心代码

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;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

测试用例

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);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步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++**实现。