C++前缀和算法的应用：最大化城市的最小供电站数目

本文涉及的基础知识点

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& 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 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 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;