We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Minimum Time Required
  2. Discussions

Minimum Time Required

  • dehaka
     + 0 comments

    ez

    let M be the min element of machines, then M*goal is 10^18 at most = 2^64 at most

    O(n * log(M * goal)), the log cannot exceed 64

    long production(long days, const vector<long>& machines) {
    long sum = 0;
    for (long x : machines) sum = sum + floor(days / x);
    return sum;
}

long minTime(vector<long> machines, long goal) {
    long low = 0, high = *min_element(machines.begin(), machines.end()) * goal;
    while (low < high) {
        long mid = (low + high) / 2;
        if (production(mid, machines) < goal) low = mid + 1;
        else high = mid;
    }
    return low;
}