3004. Очередь

В цивилизованных странах на железнодорожном вокзале работают k касс, однако очередь в них всего одна. Обслуживание происходит следующим образом. Изначально, когда все кассы свободны, первые k человек из очереди подходят к кассам. Остальные ждут своей очереди. Как только кто-нибудь будет обслужен и соответствующая касса освободится, следующий человек из очереди подходит к этой кассе. Так продолжается до тех пор, пока не будут обслужены все клиенты.

Определите время, за которое будут обслужены все клиенты.

Вход. В первой строке находится два целых числа: размер очереди n и количество касс k (1 ≤ n ≤ 10⁵, 1 ≤ k ≤ 10⁴). Во второй строке задаются n натуральных чисел. i-ое число определяет время t_i (1 ≤ t_i ≤ 10⁵), которое требуется для того, чтобы обслужить i-го клиента из очереди.

Выход. Выведите одно число – время, за которое будет обслужена заданная очередь.

Пример входа	Пример выхода
7 3 1 2 3 4 5 3 1	7

РЕШЕНИЕ

структуры данных – set, куча

Анализ алгоритма

Будем моделировать процесс продажи билетов при помощи мультимножества s. Первые k людей подводим к свободным кассам – заносим время их обслуживания в мультимножество. При дальнейшей обработке мультимножество будет содержать k элементов. Каждый их них отображает момент времени, в которое соответствующая касса станет свободной и к ней сможет подойти следующий человек. Очевидно, что каждый раз новый человек должен подходить к той кассе, для которой это время минимально. Время последнего обслуженного клиента и будет искомым.

Пример

Рассмотрим приведенный пример. Кладем в кучу k = 3 первых элементов.

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

Реализация алгоритма

Информацию о моментах времени, в которые происходит продажа билетов в кассах, храним в мультимножестве s.

multiset<long long> s;

Читаем входные данные. Время обслуживания первых k людей заносим в мультимножество s.

scanf("%d %d",&n,&k);

for(i = 0; i < n; i++)

{

scanf("%d",&ti);

if (s.size() != k) s.insert(ti);

else

{

Находим человека, который раньше всего отойдет от касс, и ставим за ним следующего человека из очереди.

long long temp = *s.begin();

s.erase(s.begin());

s.insert(temp + ti);

}

}

Наибольшее число в мультимножестве s равно моменту времени, в который обслужится последний клиент. Оно и будет искомым.

while(s.size() > 1) s.erase(s.begin());

printf("%lld\n",*s.begin());

Реализация через очередь с приоритетами

Заведем кучу, в корне которой находится наименьший элемент.

priority_queue<long long, vector<long long>, greater<long long> > pq;

Читаем входные данные. Время обслуживания первых k людей заносим в очередь pq.

scanf("%d %d",&n,&k);

for(i = 0; i < n; i++)

{

scanf("%d",&ti);

if (pq.size() != k) pq.push(ti);

else

{

Находим человека, который раньше всего отойдет от касс, и ставим за ним следующего человека из очереди.

long long temp = pq.top(); pq.pop();

pq.push(temp + ti);

}

}

Наибольшее число в очереди pq равно моменту времени, в который обслужится последний клиент. Оно и будет искомым.

while(pq.size() > 1) pq.pop();

printf("%lld\n",pq.top());

Java реализация

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

int k = con.nextInt();

PriorityQueue<Long> pq = new PriorityQueue<Long>();

for(int i = 0; i < n; i++)

{

long ti = con.nextLong();

if (pq.size() != k) pq.add(ti);

else pq.add(pq.poll() + ti);

}

while(pq.size() > 1) pq.poll();

System.out.println(pq.poll());

}

}