-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSolution.cs
More file actions
60 lines (55 loc) · 1.45 KB
/
Solution.cs
File metadata and controls
60 lines (55 loc) · 1.45 KB
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
public class Solution
{
public long MaxPower(int[] stations, int r, int k)
{
int n = stations.Length;
long[] prefix = new long[n + 1];
for (int i = 0; i < n; i++)
{
prefix[i + 1] = prefix[i] + stations[i];
}
long[] power = new long[n];
for (int i = 0; i < n; i++)
{
int left = Math.Max(0, i - r);
int right = Math.Min(n - 1, i + r);
power[i] = prefix[right + 1] - prefix[left];
}
long low = 0, high = prefix[n] + k, ans = 0;
while (low <= high)
{
long mid = low + (high - low) / 2;
if (IsValid(power, mid, r, k))
{
ans = mid;
low = mid + 1;
}
else
{
high = mid - 1;
}
}
return ans;
}
bool IsValid(long[] power, long val, int r, long k)
{
int n = power.Length;
long[] add = new long[n + 1];
long curr = 0;
for (int i = 0; i < n; i++)
{
curr += add[i];
long total = power[i] + curr;
if (total < val)
{
long need = val - total;
k -= need;
if (k < 0) return false;
curr += need;
if (i + 2 * r + 1 < n)
add[i + 2 * r + 1] -= need;
}
}
return true;
}
}