Növbə (Həll təhlili)

Bilet satışı prosesini çoxluq (multiset) $s$ vasitəsilə modelləşdirəcəyik. Əvvəlcə ilk $k$ nəfəri boş kassalara yönəldək və onların xidmət olunma vaxtını çoxluğa daxil edək.

Proses zamanı çoxluqda həmişə $k$ element olacaq, onların hər biri müvafiq kassanın nə vaxt azad olacağını və növbəti müştərini qəbul edə biləcəyini bildirir. Aydındır ki, hər yeni insan bu anı minimal olan kassaya yaxınlaşmalıdır.

Son müştərinin xidmət olunma vaxtı axtarılan qiymət olacaqdır.

Misal

Gətirilmiş misala baxaq. Əvvəlcə qalağa ilk k = 3 elementi əlavə edirik.

Sonra hər iterasiyada növbədəki sonrakı elementi (növbədəki sonrakı insanı) götürürük və onu ən kiçik elementin yerinə qoyuruq — yəni daha tez azad olacaq növbəyə. Növbəyə bu yeni insanın kassada xidmətini bitirəcəyi vaxtı əlavə edirik.

Hər şəklin yanında qalaqda olan rəqəmlər göstərilib.

Alqoritmin realizasiyası

Kassalarda bilet satışının baş verdiyi anlar haqqında məlumatı $s$ çoxluğunda saxlayırıq.

multiset\u003clong long\u003e s;

Giriş məlumatlarını oxuyuruq. İlk $k$ nəfərin xidmət olunma vaxtını $s$-ə daxil edirik.

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

Hamısından tez xidmətini bitirəcək insanı tapırıq və onun ardınca növbədəki sonrakı insanı qoyuruq.

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

$s$ çoxluğundakı ən böyük ədəd — son müştərinin xidmət olunacağı andır. Məhz bu, axtarılan qiymətdir.

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

Alqoritmin realizasiyası — prioritet növbə

Təpəsində ən kiçik element olacaq qalaq yaradaq.

priority_queue\u003clong long, vector\u003clong long\u003e, greater\u003clong long\u003e \u003e pq;

Giriş məlumatlarını oxuyuruq. İlk $k$ nəfərin xidmət olunma vaxtını $pq$ növbəsinə daxil edirik.

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

Hamısından tez xidmətini bitirəcək insanı tapırıq və onun ardınca növbədəki sonrakı insanı qoyuruq.

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

$pq$ növbəsindəki ən böyük ədəd — son müştərinin xidmət olunacağı andır. Məhz bu, axtarılan qiymətdir.

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

Java realizasiyası

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\u003cLong\u003e pq = new PriorityQueue\u003cLong\u003e();
    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());
   }
}