Skip to content

2528. Maximize the Minimum Powered City 👍

  • Time: $O(n(\Sigma |\texttt{stations[i]}| + k))$
  • Space: $O(n)$
 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
class Solution {
 public:
  long long maxPower(vector<int>& stations, int r, int k) {
    long long left = ranges::min(stations);
    long long right = accumulate(stations.begin(), stations.end(), 0LL) + k + 1;

    while (left < right) {
      const long long mid = (left + right) / 2;
      if (check(stations, r, k, mid))
        left = mid + 1;
      else
        right = mid;
    }

    return left - 1;
  }

 private:
  // Returns true if each city can have at least `minPower`.
  bool check(vector<int> stations, int r, int additionalStations,
             long long minPower) {
    const int n = stations.size();
    // Initilaize `power` as the 0-th city's power - stations[r].
    long long power = accumulate(stations.begin(), stations.begin() + r, 0LL);

    for (int i = 0; i < n; ++i) {
      if (i + r < n)
        power += stations[i + r];  // `power` = sum(stations[i - r..i + r]).
      if (power < minPower) {
        const long long requiredPower = minPower - power;
        // There're not enough stations to plant.
        if (requiredPower > additionalStations)
          return false;
        // Greedily plant `requiredPower` power stations in the farthest place
        // to cover as many cities as possible.
        stations[min(n - 1, i + r)] += requiredPower;
        additionalStations -= requiredPower;
        power += requiredPower;
      }
      if (i - r >= 0)
        power -= stations[i - r];
    }

    return true;
  }
};

 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
class Solution {
  public long maxPower(int[] stations, int r, int k) {
    long left = Arrays.stream(stations).min().getAsInt();
    long right = Arrays.stream(stations).asLongStream().sum() + k + 1;

    while (left < right) {
      final long mid = (left + right) / 2;
      if (check(stations.clone(), r, k, mid))
        left = mid + 1;
      else
        right = mid;
    }

    return left - 1;
  }

  // Returns true if each city can have at least `minPower`.
  boolean check(int[] stations, int r, int additionalStations, long minPower) {
    final int n = stations.length;
    // Initilaize `power` as the 0-th city's power - stations[r].
    long power = 0;

    for (int i = 0; i < r; ++i)
      power += stations[i];

    for (int i = 0; i < n; ++i) {
      if (i + r < n)
        power += stations[i + r]; // `power` = sum(stations[i - r..i + r]).
      if (power < minPower) {
        final long requiredPower = minPower - power;
        // There're not enough stations to plant.
        if (requiredPower > additionalStations)
          return false;
        // Greedily plant `requiredPower` power stations in the farthest place
        // to cover as many cities as possible.
        stations[Math.min(n - 1, i + r)] += requiredPower;
        additionalStations -= requiredPower;
        power += requiredPower;
      }
      if (i - r >= 0)
        power -= stations[i - r];
    }

    return true;
  }
}

 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
class Solution:
  def maxPower(self, stations: List[int], r: int, k: int) -> int:
    n = len(stations)
    left = min(stations)
    right = sum(stations) + k + 1

    # Returns true if each city can have at least `minPower`.
    def check(stations: List[int], additionalStations: int, minPower: int) -> bool:
      # Initilaize `power` as the 0-th city's power - stations[r].
      power = sum(stations[:r])

      for i in range(n):
        if i + r < n:
          power += stations[i + r]  # `power` = sum(stations[i - r..i + r]).
        if power < minPower:
          requiredPower = minPower - power
          # There're not enough stations to plant.
          if requiredPower > additionalStations:
            return False
          # Greedily plant `requiredPower` power stations in the farthest place
          # to cover as many cities as possible.
          stations[min(n - 1, i + r)] += requiredPower
          additionalStations -= requiredPower
          power += requiredPower
        if i - r >= 0:
          power -= stations[i - r]

      return True

    while left < right:
      mid = (left + right) // 2
      if check(stations.copy(), k, mid):
        left = mid + 1
      else:
        right = mid

    return left - 1