Формулировка задачи:
Организаторы детского праздника планируют надуть для него 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 секунда)?
Средний
