Требуется минимальное время Решение

Требуется минимальное время Решение

Это одна из задач средней сложности в разделе поиска набора задач Hackerrank для подготовки к собеседованию. Ссылка здесь.

Задача состоит в том, что нам дан массив из n производственных мощностей машин. Ставки показывают, сколько дней требуется машине для производства одной единицы некоторого изделия. Данные machines={1,3} означают, что у вас есть две машины, одна производит по одной каждый день, а другая производит по 1 раз в 3 дня. Теперь, учитывая производство goal, вам нужно найти минимальное количество дней, которое потребуется всем вашим машинам для достижения этой цели.

Решение

Грубое решение этой проблемы состоит в том, чтобы уменьшать цель каждый день, когда машина производит предмет, и считать дни, которые требуются, чтобы достичь нуля. Это сокращает время отправки, и мы можем добиться большего успеха.

Одно ключевое наблюдение заключается в том, что нам не нужно вычислять производительность наших машин каждый день. Учитывая любой день, мы можем вычислить производство за линейное время. Теперь рассмотрим наихудший сценарий: наша самая медленная машина сама производит все единицы, назовем ее max_days. Одним из очевидных фактов является то, что минимальное количество дней для достижения цели составляет от 1 до max_days.

Если вы знакомы с бинарным поиском, вы можете знать, к чему это приводит. Количество дней не уменьшается, поэтому мы можем использовать бинарный поиск для поиска в диапазоне возможных дней, когда мы производим не меньше требуемой производственной цели.

ОБНОВИТЬ:

После дальнейших размышлений max_days не обязательно должна быть самой медленной машиной. Поскольку только одна машина является наихудшим случаем, более точная верхняя граница поиска является самой быстрой машиной. Существует также лучшая нижняя граница fastest_machine*goal/number_of_machines Это происходит из-за того, что наша производственная цель не будет превышать фактическую производительность в день нашей цели.

Решение

ссылка на код на github

long compute_rec(vector<long> machines, long p_goal, long min_days, long max_days){
    if(machines.size()==1)
        return max_days;
    
    if(min_days == max_days)
        return min_days;
    
    long mid = ( min_days + max_days )/2;
    long production = 0;
    
    for(int i =0; i< machines.size();i++)
        production+=floor(mid/machines[i]);
    
    if(production >= p_goal)
        return compute_time_rec(machines,p_goal, min_days, mid);
    else
        return compute_time_rec(machines, p_goal, mid+1, max_days);
}
long minTime(vector<long> machines, long goal) {
    
    sort(machines.begin(), machines.end());
    return compute_rec(machines, goal, 1, machines.back()*goal);
    
}

Бонус

Вау, бонусное решение! Если вам не нравится рекурсия, вот бонусное итеративное решение. Просто вызовите его с теми же параметрами, что и рекурсивное решение. Версия в лучшем формате находится по тем же ссылкам на github, что и выше.

long compute_time_iter(vector<long> machines, long production_goal, long min_days, long max_days){
    if(machines.size()==1) return max_days;
    
    long mid;
    long production;
    
    while(min_days != max_days){
        mid = ( min_days + max_days )/2;
        production = 0;
        for(int i =0; i< machines.size();i++)
            production+=floor(mid/machines[i]);
        if(production >= production_goal)
            max_days = mid;
        else
            min_days = mid+1;
    }
    
    return min_days;
}