Черга#3004

Черга (Розбір)

Будемо моделювати процес продажу квитків за допомогою мультимножини $s$ . Спочатку підведемо до вільних кас перших $k$ людей і занесемо час їх обслуговування в мультимножину.

У процесі роботи мультимножина завжди міститиме $k$ елементів, кожен з яких позначає момент часу, коли відповідна каса звільниться і зможе прийняти наступного клієнта. Очевидно, що кожна нова людина повинна підходити до тієї каси, для якої цей момент мінімальний.

Час обслуговування останнього клієнта і буде шуканим значенням.

Приклад

Розглянемо наведений приклад. Спочатку додаємо в купу перші $k = 3$ 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
  {

C++

Знаходимо людину, яка завершить обслуговування раніше за всіх, і ставимо за нею наступну з черги.

    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
  {

C++

Знаходимо людину, яка завершить обслуговування раніше за всіх, і ставимо за нею наступну з черги.

    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());
   }
}

java++