Задать вопрос
Core2Quad777
@Core2Quad777

Как ускорить решение задачи «Детский праздник»?

Формулировка задачи:

Организаторы детского праздника планируют надуть для него m
воздушных шариков. С этой целью они пригласили n добровольных помощников, i-й среди которых надувает шарик за ti минут, однако каждый раз после надувания zi шариков устает и отдыхает yi минут. Теперь организаторы праздника хотят узнать, через какое время будут надуты все шарики при наиболее оптимальной работе помощников. (Если помощник надул шарик, и должен отдохнуть, но больше шариков ему надувать не придется, то считается, что он закончил работу сразу после окончания надувания последнего шарика, а не после отдыха).

Ограничения:
1 ≤ N ≤10^5
1 ≤ M ≤ 10^8
0 ≤ Zi, Ti, Yi ≤ 10^9

Мои решения не проходят по времени для данных ограничений.

1. Стандартное решение этой задачи через бин.поиск:

#include <iostream>
#include <vector>
using namespace std;

long long m, n;
vector<long long> t, z, y;

long long counter_max(long long i, long long T, vector<long long> t, vector<long long> z,  vector<long long> y) {
   long long C = 0;
   while(T >= t[i]) {
       T -= t[i];
       if (++C%z[i] == 0) {
           T -= y[i];
       }
   }
   return C;
}

bool can(long long T, vector<long long> t, vector<long long> z,  vector<long long> y) {
   long long K = 0;
   for (long long i = 0; i < n; i++){
       K += counter_max(i, T, t, z, y);  
   }
   return K >= m;
}

int main() {
   cin >> m >> n;
   vector<long long> t(n), z(n), y(n);
   for (long long i = 0; i < n; i++) {
       cin >> t[i] >> z[i] >> y[i];
   }
   long long low = 0;
   long long high = 1000000001;
   while (low < high) {
       long long T = (low + high) / 2;
       if (can(T, t, z, y)) {
           high = T;
       } else {
           low = T + 1;
       }
   }
   cout << high;
   return 0;
}

2. Решение на python через кучи (на c++ через кучи также не проходит):

import heapq
 
m,n = map(int, input().split())
t,z,y = map(list,zip(*[map(int, input().split()) for _ in range(n)]))
counter = [0]*n
times = list(zip(t,range(n)))
heapq.heapify(times)
for _ in range(m):
    next_time, i = heapq.heappop(times)
    counter[i] += 1
    heapq.heappush(times, (next_time + t[i] + y[i]*(counter[i]%z[i]==0), i))
print(next_time)

Как ускорить решение, чтобы оно проходило по времени (лимит 1 секунда)?
  • Вопрос задан
  • 823 просмотра
Подписаться 1 Средний Комментировать
Решения вопроса 2
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Бинпоиск - правильная идея. Но вот вы плохо считаете, сколько шариков один работник надует за заданное время. Вы линейно по одному шарику надуваете, а можно за 2 действия: поделите время на ti*zi+ci - узнаете, сколько полных групп шариков надуется. Остаток отдельно подсчитайте, поделив на ti. Учтите только, что оставшееся время может быть прервано на отдыхе - не насчитайте там больше zi шаров по ощибке.

Решение через кучи страдает той же проблемой - вы по одиночке каждый шар считаете, а их очень-очень много.
Ответ написан
trapwalker
@trapwalker
Программист, энтузиаст
Вижу один ответ уже пометили как правильный, но ворвусь сюда со своею лептой.
Очевидно, что при огромных значениях m и малых допуска по времени тут от решения ожидается какая-то радикальная оптимизация, а не полный перебор по одному шарику.

А оптимизировать можно вот так.
Давайте сперва представим, что надувальщикам не надо отдыхать и они шпарят каждый со своею скоростью шарики.
Тогда можно сложить производительность каждого (1/t[i] -- шаров в минуту) и в сумме получим общую производительность толпы из N надувальщиков. Посчитать время теперь можно за один шаг по формуле.
Теперь вспоминаем, что разные надувальщики будут в разное время отдыхать.
Очевидно, что всё время их работы разобьётся на сегменты с различной производительностью, ведь надувают в рамках каждого сегмента разные надувальщики с разной собственной скоростью.
Итак, первый сегмент будет с полной суммарной производительностью всех надувальщиков и длиться он будет вот сколько времени в минутах: T[j]=min(t[i]*z[i] for i in range(n)), но надуют они за это время много шаров с общей суммарной производительностью. В момент T[j] начнётся новый сегмент, в котором одного надувальщика не будет, он ушел на отдых и этот отдых будет длиться какое-то время r. Для следующего сегмента нужно посчитать новую производительность всех оставшихся участников. Можно из предыдущей производительности вычесть производительность выбывшего. Новый сегмент будет длиться, скорее всего, меньше. Нужно взять минимум между оставшимися временами работы оставшихся надувальщиков и временем r. То есть новый сегмент будет не длиннее r и продлится пока не выдохнется следующий из оставшихся надувальщиков. Так в каждом сегменте будет свой набор и своя производительность, каждый сегмент надует своё число шаров и как только оно перевалит за m нужно посчитать остаток последнего сегмента и сумма длин сегментов будет ответом.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы