[LeetCode] 2141. Maximum Running Time of N Computers

https://leetcode.com/problems/maximum-running-time-of-n-computers/description/?envType=daily-question&envId=2025-12-01

Leetcode - Maximum Runnging Time of N Computers

문제 유형: 이진탐색, 매개 변수 탐색, 그리디

문제 난이도: Hard

 

문제

You have n computers. You are given the integer n and a 0-indexed integer array batteries where the ith battery can run a computer for batteries[i] minutes. You are interested in running all n computers simultaneously using the given batteries.

Initially, you can insert at most one battery into each computer. After that and at any integer time moment, you can remove a battery from a computer and insert another battery any number of times. The inserted battery can be a totally new battery or a battery from another computer. You may assume that the removing and inserting processes take no time.

Note that the batteries cannot be recharged.

Return the maximum number of minutes you can run all the n computers simultaneously.

 

n개의 컴퓨터가 있다. batteries배열이 주어지는데, batteries[i]는 i번째 배터리가 지속가능한 시간을 말한다.

당신은 이 주어진 배터리들로 동시에 n개의 컴퓨터를 모두 켜놓을 수 있는 최대 시간을 구하고 싶다.

배터리를 교체하는 횟수에는 제한이 없고, 시간이 소모되지 않는다고 가정한다.

 

 

 

풀이

파라메트릭 서치 문제이다.

최소값은 0이 될 수 있고, 최대 sum / n분까지 켤 수 있다.

t분동안 컴퓨터들을 가동한다고 할때, 각 배터리는 최대 min(t, batteries[i])만큼만 켤 수 있음을 알 수 있다.

lo = 0, hi = sum / n까지 하고, mid를 둘의 중점으로 계산해서, t로 둔다. 

만약 이번 mid분으로 가능하다면, ans에 t를 저장하고, 더 큰 수를 노리기 위해, lo = mid + 1로 업데이트한다.

안된다면, 더 낮은 범위를 고르기 위해 hi = mid - 1로 업데이트한다.

이를 lo <= hi인동안 반복한다.

 

최종적 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:
    bool check(ll time, int n, vector<int>& batteries) {
        ll tot = 0;
        for (ll b : batteries) {
            tot += min(b, time);
        }

        return tot >= time * n;
    }
    long long maxRunTime(int n, vector<int>& batteries) {
        ll sum = accumulate(batteries.begin(), batteries.end(), 0LL);

        ll lo = 0;
        ll hi = sum / n;
        ll ans = 0;

        while (lo <= hi) {
            ll mid = (lo + hi) >> 1;
            if (check(mid, n, batteries)) {
                ans = mid;
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }

        return ans;
    }
};

 

Go

func maxRunTime(n int, batteries []int) int64 {
	ans := int64(0)
	lo := int64(0)
	hi := int64(0)
	for _, bat := range batteries {
		hi += int64(bat)
	}
	hi /= int64(n)

	for lo <= hi {
		mid := (lo + hi) >> 1
		if check(mid, n, batteries) {
			ans = mid
			lo = mid + 1
		} else {
			hi = mid - 1
		}
	}

	return ans
}

func check(time int64, n int, batteries []int) bool {
	tot := int64(0)

	for _, b := range batteries {
		tot += min(int64(b), time)
	}

	return tot >= time*int64(n)
}

 

Rust

impl Solution {
    pub fn max_run_time(n: i32, batteries: Vec<i32>) -> i64 {
        let n = n as i64;
        let mut batteries: Vec<i64> = batteries.into_iter().map(|x| x as i64).collect();

        let sum: i64 = batteries.iter().sum();

        let mut lo: i64 = 0;
        let mut hi: i64 = sum / n;
        let mut ans: i64 = 0;

        while lo <= hi {
            let mid = (lo + hi) / 2;

            if Self::check(mid, n, &batteries) {
                ans = mid;
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }

        ans
    }

    fn check(time: i64, n: i64, batteries: &Vec<i64>) -> bool {
        let mut tot: i64 = 0;
        for &b in batteries {
            tot += b.min(time);
        }
        tot >= n * time
    }
}