Welcome to Subscribe On Youtube

2528. Maximize the Minimum Powered City

Description

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

Solutions

  • class Solution {
        private long[] s;
        private long[] d;
        private int n;
    
        public long maxPower(int[] stations, int r, int k) {
            n = stations.length;
            d = new long[n + 1];
            s = new long[n + 1];
            for (int i = 0; i < n; ++i) {
                int left = Math.max(0, i - r), right = Math.min(i + r, n - 1);
                d[left] += stations[i];
                d[right + 1] -= stations[i];
            }
            s[0] = d[0];
            for (int i = 1; i < n + 1; ++i) {
                s[i] = s[i - 1] + d[i];
            }
            long left = 0, right = 1l << 40;
            while (left < right) {
                long mid = (left + right + 1) >>> 1;
                if (check(mid, r, k)) {
                    left = mid;
                } else {
                    right = mid - 1;
                }
            }
            return left;
        }
    
        private boolean check(long x, int r, int k) {
            Arrays.fill(d, 0);
            long t = 0;
            for (int i = 0; i < n; ++i) {
                t += d[i];
                long dist = x - (s[i] + t);
                if (dist > 0) {
                    if (k < dist) {
                        return false;
                    }
                    k -= dist;
                    int j = Math.min(i + r, n - 1);
                    int left = Math.max(0, j - r), right = Math.min(j + r, n - 1);
                    d[left] += dist;
                    d[right + 1] -= dist;
                    t += dist;
                }
            }
            return true;
        }
    }
    
  • class Solution {
    public:
        long long maxPower(vector<int>& stations, int r, int k) {
            int n = stations.size();
            long d[n + 1];
            memset(d, 0, sizeof d);
            for (int i = 0; i < n; ++i) {
                int left = max(0, i - r), right = min(i + r, n - 1);
                d[left] += stations[i];
                d[right + 1] -= stations[i];
            }
            long s[n + 1];
            s[0] = d[0];
            for (int i = 1; i < n + 1; ++i) {
                s[i] = s[i - 1] + d[i];
            }
            auto check = [&](long x, int k) {
                memset(d, 0, sizeof d);
                long t = 0;
                for (int i = 0; i < n; ++i) {
                    t += d[i];
                    long dist = x - (s[i] + t);
                    if (dist > 0) {
                        if (k < dist) {
                            return false;
                        }
                        k -= dist;
                        int j = min(i + r, n - 1);
                        int left = max(0, j - r), right = min(j + r, n - 1);
                        d[left] += dist;
                        d[right + 1] -= dist;
                        t += dist;
                    }
                }
                return true;
            };
            long left = 0, right = 1e12;
            while (left < right) {
                long mid = (left + right + 1) >> 1;
                if (check(mid, k)) {
                    left = mid;
                } else {
                    right = mid - 1;
                }
            }
            return left;
        }
    };
    
  • class Solution:
        def maxPower(self, stations: List[int], r: int, k: int) -> int:
            def check(x, k):
                d = [0] * (n + 1)
                t = 0
                for i in range(n):
                    t += d[i]
                    dist = x - (s[i] + t)
                    if dist > 0:
                        if k < dist:
                            return False
                        k -= dist
                        j = min(i + r, n - 1)
                        left, right = max(0, j - r), min(j + r, n - 1)
                        d[left] += dist
                        d[right + 1] -= dist
                        t += dist
                return True
    
            n = len(stations)
            d = [0] * (n + 1)
            for i, v in enumerate(stations):
                left, right = max(0, i - r), min(i + r, n - 1)
                d[left] += v
                d[right + 1] -= v
            s = list(accumulate(d))
            left, right = 0, 1 << 40
            while left < right:
                mid = (left + right + 1) >> 1
                if check(mid, k):
                    left = mid
                else:
                    right = mid - 1
            return left
    
    
  • func maxPower(stations []int, r int, k int) int64 {
    	n := len(stations)
    	d := make([]int, n+1)
    	s := make([]int, n+1)
    	for i, v := range stations {
    		left, right := max(0, i-r), min(i+r, n-1)
    		d[left] += v
    		d[right+1] -= v
    	}
    	s[0] = d[0]
    	for i := 1; i < n+1; i++ {
    		s[i] = s[i-1] + d[i]
    	}
    	check := func(x, k int) bool {
    		d := make([]int, n+1)
    		t := 0
    		for i := range stations {
    			t += d[i]
    			dist := x - (s[i] + t)
    			if dist > 0 {
    				if k < dist {
    					return false
    				}
    				k -= dist
    				j := min(i+r, n-1)
    				left, right := max(0, j-r), min(j+r, n-1)
    				d[left] += dist
    				d[right+1] -= dist
    				t += dist
    			}
    		}
    		return true
    	}
    	left, right := 0, 1<<40
    	for left < right {
    		mid := (left + right + 1) >> 1
    		if check(mid, k) {
    			left = mid
    		} else {
    			right = mid - 1
    		}
    	}
    	return int64(left)
    }
    
  • function maxPower(stations: number[], r: number, k: number): number {
        function check(x: bigint, k: bigint): boolean {
            d.fill(0n);
            let t = 0n;
            for (let i = 0; i < n; ++i) {
                t += d[i];
                const dist = x - (s[i] + t);
                if (dist > 0) {
                    if (k < dist) {
                        return false;
                    }
                    k -= dist;
                    const j = Math.min(i + r, n - 1);
                    const left = Math.max(0, j - r);
                    const right = Math.min(j + r, n - 1);
                    d[left] += dist;
                    d[right + 1] -= dist;
                    t += dist;
                }
            }
            return true;
        }
        const n = stations.length;
        const d: bigint[] = new Array(n + 1).fill(0n);
        const s: bigint[] = new Array(n + 1).fill(0n);
    
        for (let i = 0; i < n; ++i) {
            const left = Math.max(0, i - r);
            const right = Math.min(i + r, n - 1);
            d[left] += BigInt(stations[i]);
            d[right + 1] -= BigInt(stations[i]);
        }
    
        s[0] = d[0];
        for (let i = 1; i < n + 1; ++i) {
            s[i] = s[i - 1] + d[i];
        }
    
        let left = 0n,
            right = 1n << 40n;
        while (left < right) {
            const mid = (left + right + 1n) >> 1n;
            if (check(mid, BigInt(k))) {
                left = mid;
            } else {
                right = mid - 1n;
            }
        }
        return Number(left);
    }
    
    

All Problems

All Solutions