넘치게 채우기
[LeetCode] 2528. Maximize the Minimum Powered City 본문
Leetcode - Maximize the Minimum Powered City
문제 유형: 슬라이딩 윈도우, 누적 합, 이진 탐색
문제 난이도: Hard
문제
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.
i번째 도시의 power는 i-r ~ i+r범위의 station값의 합이다.
정부는 k개의 발전소를 더하려고 한다.
k개를 적절히 추가배치한 경우, 최소 power값이 최대가 되는 값이 얼마인지 구하시오.
풀이
Maximize the minimum = 곧 Parametric search 문제이다.
우선, 누적 합 배열을 만들어준다.
가능한 답의 범위는 0 ~ (전체 합 + k)로 잡았다.
즉, lo = 0, hi = pref[n-1] + k로 한다.
이제, 이러면 투 포인터를 이용해서 쉽게 범위의 합을 구할 수 있어진다.
lo <= hi인동안, 다음을 시행한다:
- mid = (lo+hi)/2로 중간점을 찍는다.
- 배열의 최소 power값을 mid값으로 하는걸 목표로 시뮬레이션을 돌린다.
- k개 이내로 가능하다면, 더 큰 목표를 한다. 우선, 마지막 성공값인 mid를 ans에 저장하고, lo = mid+1로 새로 범위를 잡는다.
- 불가능하다면, 더 작은 목표를 위해 hi = mid-1로 한다.
최종적으로 ans를 리턴하면 된다.
코드
C++
#pragma GCC optimize("O3", "unroll-loops");
static const int __ = []() {
ios::sync_with_stdio(0);
cin.tie(0);
return 0;
}();
using ll = long long;
class Solution {
public:
int n;
bool solve(ll target, vector<ll>& pref, int r, ll k) {
vector<ll> added(n, 0);
ll extrasum = 0;
for (int i = 0; i < n; i++) {
int leftIdx = max(i - r - 1, 0);
int rightIdx = min(n - 1, i + r);
ll left = i - r - 1 >= 0 ? pref[i - r - 1] : 0;
ll right = pref[rightIdx];
extrasum -= added[leftIdx];
ll sum = right - left + extrasum;
ll diff = target - sum;
if (diff > 0) {
if (k - diff < 0) return false;
added[rightIdx] += diff;
extrasum += diff;
k -= diff;
}
}
return true;
}
long long maxPower(vector<int>& stations, int r, int k) {
this->n = stations.size();
vector<ll> pref(n, 0);
pref[0] = stations[0];
for (int i = 1; i < n; i++) {
pref[i] = pref[i - 1] + stations[i];
}
ll lo = 0, hi = pref.back() + k, ans = 0;
while (lo <= hi) {
ll mid = (lo + hi) >> 1;
if (solve(mid, pref, r, k)) {
ans = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return ans;
}
};
Go
type Solver struct {
n int
r int
k int64
pref []int64
}
func NewSolver(stations []int, r int, k int) *Solver {
n := len(stations)
pref := make([]int64, n)
pref[0] = int64(stations[0])
for i := 1; i < n; i++ {
pref[i] = pref[i-1] + int64(stations[i])
}
return &Solver{n, r, int64(k), pref}
}
func (s *Solver) check(target int64) bool {
added := make([]int64, s.n)
extraSum := int64(0)
k := s.k
for i := 0; i < s.n; i++ {
leftIdx := max(i-s.r-1, 0)
rightIdx := min(i+s.r, s.n-1)
var left int64
if i-s.r-1 >= 0 {
left = s.pref[leftIdx]
} else {
left = 0
}
right := s.pref[rightIdx]
extraSum -= added[leftIdx]
sum := right - left + extraSum
diff := target - sum
if diff > 0 {
if k-diff < 0 {
return false
}
added[rightIdx] += diff
extraSum += diff
k -= diff
}
}
return true
}
func (s *Solver) solve() int64 {
var res int64
lo, hi := int64(0), s.pref[s.n-1]+s.k
for lo <= hi {
mid := (lo + hi) >> 1
if s.check(mid) {
res = mid
lo = mid + 1
} else {
hi = mid - 1
}
}
return res
}
func maxPower(stations []int, r int, k int) int64 {
s := NewSolver(stations, r, k)
return s.solve()
}