题目描述：
给你一个下标从 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\le n \le 10^5, 0 \le k \le 10^9, 0 \le stations[i] \le 10^5$
题解：
最小值最大，二分check
可以先使用前缀和算出来每个位置的电力数量，方便后面check。
check时，可以先遍历到小于 $mid$ 的位置，然后贪心的在最右边加供电站，这样的话区间加。可以使用差分数组，然后对差分数组进行区间加操作，计算每个位置的电力值时，需要和差分数组累加。
代码：
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
bool check(long long mid, vector<long long> &tot, int r, int k)
{
int n = tot.size() - 1;
vector<long long> diff(n + 1);
long long cnt = 0;
long long presum = 0;
for (int i = 1; i <= n; ++i)
{
presum += diff[i];
if (presum + tot[i] < mid)
{
long long need = mid - presum - tot[i];
cnt += need;
if (cnt > k)
return false;
if (i + 1 <= n)
diff[i + 1] += need;
if (i + 2 * r + 1 <= n)
diff[i + 2 * r + 1] -= need;
}
}
return cnt <= k;
}
long long maxPower(vector<int> &stations, int range, int k)
{
int n = stations.size();
int minx = INF;
vector<long long> preSum(n + 1);
vector<long long> tot(n + 1);
for (int i = 1; i <= n; ++i)
preSum[i] = preSum[i - 1] + stations[i - 1];
for (int i = 1; i <= n; ++i)
{
int l = max(1, i - range);
int r = min(n, i + range);
tot[i] = preSum[r] - preSum[l - 1];
}
long long l = 0, r = preSum[n] + k;
long long ans = 0;
while (l <= r)
{
long long mid = l + r >> 1;
if (check(mid, tot, range, k))
{
l = mid + 1;
ans = mid;
}
else
r = mid - 1;
}
return ans;
}
};
|