Today I have done leetcode's November LeetCoding Challenge with cpp.

November LeetCoding Challenge 7

Description

Maximize the Minimum Powered City

You are given a 0-indexed integer array stations of length n, where stations[i] represents the number of power stations in the ith city.

Each power station can provide power to every city in a fixed range. In other words, if the range is denoted by r, then a power station at city i can provide power to all cities j such that |i - j| <= r and 0 <= i, j <= n - 1.

• Note that |x| denotes absolute value. For example, |7 - 5| = 2 and |3 - 10| = 7.

The power of a city is the total number of power stations it is being provided power from.

The government has sanctioned building k more power stations, each of which can be built in any city, and have the same range as the pre-existing ones.

Given the two integers r and k, return the maximum possible minimum power of a city, if the additional power stations are built optimally.

Note that you can build the k power stations in multiple cities.

Example 1:

Input: stations = [1,2,4,5,0], r = 1, k = 2
Output: 5
Explanation: 
One of the optimal ways is to install both the power stations at city 1. 
So stations will become [1,4,4,5,0].
- City 0 is provided by 1 + 4 = 5 power stations.
- City 1 is provided by 1 + 4 + 4 = 9 power stations.
- City 2 is provided by 4 + 4 + 5 = 13 power stations.
- City 3 is provided by 5 + 4 = 9 power stations.
- City 4 is provided by 5 + 0 = 5 power stations.
So the minimum power of a city is 5.
Since it is not possible to obtain a larger power, we return 5.

Example 2:

Input: stations = [4,4,4,4], r = 0, k = 3
Output: 4
Explanation: 
It can be proved that we cannot make the minimum power of a city greater than 4.

Constraints:

• n == stations.length
• 1 <= n <= 105
• 0 <= stations[i] <= 105
• 0 <= r <= n - 1
• 0 <= k <= 109

Solution

template<typename T>
std::ostream& operator<<(std::ostream &out, const std::vector<T> &v) {
  if(v.size() == 0) {
    out << "[]" << std::endl;
    return out;
  }
  out << '[' << v[0];
  for(int i = 1; i < v.size(); ++i) {
    out << ", " << v[i];
  }
  out << ']';
  return out;
}
class Solution {
  int n;
  bool check(const vector<long long> &power, vector<int> &change, long long target, int k, int r) {
    fill(change.begin(), change.end(), 0);
    long long accumulate = 0;
    for(int i = 0; i < n; ++i) {
      if(i > r) accumulate -= change[i - r - 1];
      long long current = power[i] + accumulate;
      if(current >= target) continue;
      if(current + k < target) return false;
      int pos = min(n - 1, i + r);
      change[pos] = target - current;
      accumulate += target - current;
      k -= target - current;
    }
    return true;
  }
public:
  long long maxPower(vector<int>& stations, int r, int k) {
    n = stations.size();
    if(n == 1) return stations[0] + 0ll + k;
    vector<long long> power(n);
    for(int i = 0; i <= r; ++i) {
      power[0] += stations[i];
    }
    for(int i = 1; i < n; ++i) {
      power[i] = power[i - 1];
      if(i + r < n) power[i] += stations[i + r];
      if(i > r) power[i] -= stations[i - r - 1];
    }
    long long low = *min_element(power.begin(), power.end());
    long long high = *max_element(power.begin(), power.end()) + k;
    vector<int> tmp(n);

    while(low < high) {
      long long mid = (low + high + 1) / 2;
      if(check(power, tmp, mid, k, r)) {
        low = mid;
      } else {
        high = mid - 1;
      }
    }
    return low;
  }
};

// Accepted
// 30/30 cases passed (63 ms)
// Your runtime beats 95.27 % of cpp submissions
// Your memory usage beats 98.11 % of cpp submissions (76.3 MB)