Coda (Editoriale)

Modelleremo il processo di vendita dei biglietti tramite un multiinsieme $s$. Innanzitutto, facciamo avvicinare alle casse libere le prime $k$ persone e inseriamo il loro tempo di servizio nel multiinsieme.

Durante il processo di lavoro, il multiinsieme conterrà sempre $k$ elementi, ciascuno dei quali indica il momento in cui la cassa corrispondente si libererà e potrà accogliere il cliente successivo. È evidente che ogni nuova persona debba avvicinarsi alla cassa per cui questo momento è minimo.

Il tempo di servizio dell'ultimo cliente sarà il valore cercato.

Esempio

Consideriamo l'esempio riportato. Per prima cosa aggiungiamo nello heap i primi k = 3 elementi.

In seguito, a ogni iterazione, prendiamo l'elemento successivo (la persona successiva in coda) e lo mettiamo al posto del più piccolo — nella coda che si libererà prima. Nella coda aggiungiamo il momento in cui questa nuova persona terminerà il servizio alla cassa.

Accanto a ogni figura sono indicati i numeri presenti nello heap.

Implementazione dell'algoritmo

Le informazioni sui momenti in cui avviene la vendita dei biglietti alle casse vengono memorizzate nel multiinsieme $s$.

multiset
s;

Leggiamo i dati in input. Il tempo di servizio delle prime $k$ persone viene inserito in $s$.

scanf("%d %d",&n,&k);
for(i = 0; i < n; i++)
{
  scanf("%d",&ti);
  if (s.size() != k) s.insert(ti);
  else
  {

Troviamo la persona che terminerà il servizio prima di tutte e mettiamo dietro di lei la persona successiva in coda.

    long long temp = *s.begin();
    s.erase(s.begin()); 
    s.insert(temp + ti);
  }
}

Il numero più grande nel multiinsieme $s$ — è il momento in cui verrà servito l'ultimo cliente. Esso è il valore cercato.

while(s.size() > 1) s.erase(s.begin());
printf("%lld\n",*s.begin());

Implementazione dell'algoritmo — coda con priorità

Creiamo uno heap, alla cui radice si troverà l'elemento più piccolo.

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

Leggiamo i dati in input. Il tempo di servizio delle prime $k$ persone viene inserito nella coda $pq$.

scanf("%d %d",&n,&k);
for(i = 0; i < n; i++)
{
  scanf("%d",&ti);
  if (pq.size() != k) pq.push(ti);
  else
  {

Troviamo la persona che terminerà il servizio prima di tutte e mettiamo dietro di lei la persona successiva in coda.

    long long temp = pq.top(); pq.pop();
    pq.push(temp + ti);
  }
}

Il numero più grande nella coda $pq$ — è il momento in cui verrà servito l'ultimo cliente. Esso è il valore cercato.

while(pq.size() > 1) pq.pop();
printf("%lld\n",pq.top());

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