Zadanie

“2016? No do ….. bre.” zahundral hračkár Hilbert. Rozlepil oči, utrel si zemiakový šalát tečúci z ucha a dal si rozbehový krémeš na dobré ráno. Sviatky ako majú byť. Treba ale ísť do práce a urobiť koncoročnú uzávierku. Vianoce sú totiž každoročne výdatné na zákazníkov a aj na tržby. Hilbert už presne vie, ako to funguje. Do obchodu príde človek a kúpi prvý darček, ktorý mu je ponúknutý. Človek zaň zaplatí a beží do ďalšieho obchodu. Je prakticky jedno, o aký predmet sa jedná. Dokonca ani nezáleží na cene, pokiaľ nie je príliš vysoká. Všetko závisí od toho, ako málo času ostáva do Vianoc – čím menej času, tým väčšie výčitky svedomia má konkrétny nešťastník, a tým viac je ochotný za darček zaplatiť.

Hilbertovi sa stačí pozrieť na hodinky a hneď vie, koľko peňazí môže zákazník minúť. No a to sa dá úžasne využiť. Stačí vždy nájsť najdrahší darček, ktorý je daný človek ešte ochotný kúpiť a ponúknuť mu ho. Hilbertovo podnikavé srdce teraz kruto zaplakalo. Tento prešibaný plán počas minulého roka ani raz nepoužil… To sa však s novým rokom zmení!

Hilbert by predsa len rád vedel, ako by bol jeho biznis prekvital, ak by túto metódu použil už predošlé Vianoce. Podarilo sa mu zrekonštruovať zoznam ľudí, ktorí prišli do jeho obchodu, no nie je si úplne istý, koľko mohol na každom z nich zarobiť.

Úloha

Na vstupe máte vzostupne usporiadané ceny darčekov v Hilbertovom obchode. Postupne k nemu prichádzajú ľudia. Každý človek má maximálne množstvo peňazí, ktoré je ochotný minúť na darček. Človek, ktorý príde neskôr bude vždy ochotný minúť aspoň toľko ako ten, čo prišiel pred ním. Pre každého človeka vypíšte cenu najdrahšieho darčeka, ktorý si ešte môže dovoliť, a ktorý mu teda Hilbert ponúkne. Po tom, čo si ho zákazník kúpi, ho už Hilbert nemôže ponúkať ďalej.

Formát vstupu

Na prvom riadku sú dve čísla \(n\) a \(m\) (\(1 \leq n \leq 1\,000\,000\), \(1 \leq m \leq 1\,000\,000\)) – počet darčekov, ktoré má Hilbert v obchode a počet zákazníkov, ktorý k nemu prídu.

Na druhom riadku je vzostupne usporiadaná postupnosť \(n\) kladných celých čísel \(c_i\) (\(1\leq c_i \leq 10^9\)) – ceny darčekov v Hilbertovom obchode.

Na treťom riadku je vzostupne usporiadaná postupnosť \(m\) kladných celých čísel \(p_i\) (\(1\leq p_i \leq 10^9\)) – množstvo peňazí, ktoré je ochotný minúť \(i\)-ty zákazník.

V polovici sád navyše platí, že \(1 \leq n \leq 1\,000\) a \(1 \leq m \leq 1\,000\).

Formát výstupu

Pre každého zákazníka vypíšte cenu najdrahšieho darčeka, ktorý mu môže Hilbert ponúknuť. Ak taký nie je, vypíšte \(0\).

Príklad

Input:

8 10
1 2 2 2 5 7 10 20
1 1 2 3 6 6 15 21 21 22

Output:

1 0 2 2 5 2 10 20 7 0

Druhému zákazníkovi nevie Hilbert ponúknuť žiadny darček, lebo jediný predmet s cenou nanajvýš 1 si kúpil prvý zákazník. Takisto si všimnite, že aj keď je deviaty zákazník ochotný za darček zaplatiť až cenu 21, Hilbert mu vie ponúknuť iba predmet s cenou 7, lebo zvyšné rozpredal predošlým zákazníkom.

Najjednoduchšie, čo môžeme spraviť, je celú situáciu simulovať. Budeme si jednoducho pamätať všetky darčeky, ktoré ešte Hilbert nepredal, a postupne ich predávať. Otázkou je, ako to vieme robiť rýchlo.

Riešenie hrubou silou

Stačí mať jedno pole (C++ vector), v ktorom si udržiavame ceny ešte nepredaných darčekov. Na ňom potom potrebujeme robiť nasledovné operácie:

  1. Nájdenie darčeku s najvyššou cenou neprevyšujúcou nejakú hranicu
  2. Predanie (odstránenie) darčeka

Operáciu 1 vieme robiť triviálne v čase \(O(n)\). Stačí prejsť všetky darčeky a pamätať si, aký najdrahší sme zatiaľ videli. Odstraňovanie darčeku je za normálnych okolností tiež lineárne, lebo musíme posunúť všetky darčeky za ním. Dá sa ale urobiť finta na skonštantnenie tohoto času. Môžeme totiž najprv vymeniť chcený darček s posledným a potom iba vector o jedna skrátiť. Podobne by sme daný darček mohli len prepísať na \(0\). S časovou zložitosťou si ale aj tak veľmi nepomôžeme.

Pre každého človeka, čo príde do obchodu, musíme nájsť darček v \(O(n)\) a teda dostaneme riešenie v čase \(O(nm)\) s pamäťou \(O(n)\), ktoré nám získa \(2\) body.

#include <cstdio>

int darceky [1000000];             //vsetky darceky

int main () {
  int n, m;
  scanf("%d %d ", &n, &m);
  for(int i = 0; i < n; i++)
    scanf("%d ", &darceky[i]);

  bool je_prve = true;
  
  for(int i = 0; i < m; i++){
    int clovek;
    scanf("%d ", &clovek);
    int max = 0;
    int kde = 0;
    for(int j = 0; j < n; j++){    //najdeme najdrahsi vyhovujuci darcek
      if (max < darceky[j] && darceky[j] <= clovek){
        max = darceky[j];
        kde = j;
      }
    }
    
    if(!je_prve)                   //pekne vypisovanie
      printf(" ");
    je_prve = false;
    printf("%d", max);

    if(max > 0){
      darceky[kde] = 0;            //odstranime darcek
  }
  
  printf("\n");
  return 0;
}

Mohlo by nám napadnúť, že operácia 1 sa by sa mohla dať vyriešiť binárnym vyhľadávaním. Potom by sme ju vedeli robiť v \(O(\log(n))\). Problém ale je, že pre operáciu 2 by sme nevedeli použiť našu fintu (tá totiž nezachováva usporiadanie) a stále by sme ostali na čase \(O(nm)\).

Riešenie hrubou STL1 silou

Binárne vyhľadávanie nám síce veľmi nepomohlo, binárny vyhľadávací strom nám ale pomôcť môže. Je to štruktúra, ktorá zvláda pridávanie nových prvkov, vymazávanie a vyhľadávanie prvkov a to všetko v čase \(O(\log(n))\). Takáto funkcionalita je už implementovaná v štandardnej C++kovej knižnici pod krycím názvom multiset. Stačí túto čarovnú štruktúru inicializovať, naplniť ju darčekmi, a potom v nej len vyhľadávať pomocou metódy lower_bound a vymazávať pomocou erase. Nakoľko pridávanie je logaritmické, vieme ju naplniť v čase \(O(n\log(n))\) a pre každého človeka vyhľadávať a mazať tiež v \(O(\log(n))\). Dostaneme teda riešenie v čase \(O(n\log(n) + m\log(n))\). Vďaka tomu, že sú darčeky na vstupe usporiadané, je vkladanie možné aj v konštantnom čase a teda výsledná časová zložitosť by bola len \(O(n + m\log(n))\), čo ale nie je podstatné zlepšenie. Pamäťovú zložitosť máme stále \(O(n)\). Toto riešenie je dostatočne rýchle pre všetky testovacie sady, no plný počet za popis neprinesie.

#include <cstdio>
#include <set>

using namespace std;

int main () {
  int n, m;
  int pom;
  multiset<int> darceky;
  multiset<int>::iterator it;
  bool je_prve = true;
  scanf("%d %d ", &n, &m);
  for(int i = 0; i < n; i++){
    scanf("%d ", &pom);
    darceky.insert(-pom);              //lebo set vie vracat len vacsie veci
  }
  
  for(int i = 0; i < m; i++){
    int clovek;
    scanf("%d ", &clovek);
    it = darceky.lower_bound(-clovek);
    
    if(!je_prve)
      printf(" ");
    je_prve = false;
    
    if(it != darceky.end()){           //toto vrati lower_bound ked nieco v sete nie je
      printf("%d", -(*it));
      darceky.erase(it);
    }
    else{
      printf("0");
    }
  }
  printf("\n");
  
  return 0;
}

Optimálne riešenie

Zatiaľ sme takmer vôbec nevyužili usporiadanie darčekov a ľudí na vstupe. To by nám mohlo napovedať, že ešte nemáme optimálne riešenie. Predstavme si nasledujúcu situáciu: do obchodu príde Ferko a kúpi nejaký darček. Keď po ňom príde Jožko, aký darček kúpi? Jožko je určite aspoň tak bohatý ako Ferko. Buď si kúpi niečo, čo mohol kúpiť aj Ferko, alebo kúpi niečo, čo si Ferko nemohol dovoliť. Inak povedané, keď prišiel do obchodu Ferko, mal množinu darčekov, ktoré si mohol dovoliť. Z nej si vybral ten najdrahší. Keď potom prišiel Jožko, tiež mal množinu darčekov, ktoré si mohol dovoliť. V nej boli všetky tie darčeky, čo si mohol dovoliť Ferko (okrem toho, ktorý si Ferko kúpil) a všetky, ktoré si Ferko kúpiť nemohol, no Jožko už áno.

To znamená, že nám stačí udržiavať množinu kúpiteľných a množinu nekúpiteľných darčekov. Keď príde nový človek, presunieme z nekúpiteľných do kúpiteľných všetky darčeky, ktoré si daný človek už môže dovoliť. Teda niekoľko najlacnejších nekúpiteľných darčekov prehlásime za kúpiteľné. Potom zistíme, či je množina kúpiteľných darčekov prázdna a ak nie je, predáme z nej najdrahší darček. Na začiatku sú všetky darčeky nekúpiteľné a vieme, že na vstupe sú vzostupne usporiadané. Vďaka tomu si môžeme nekúpiteľné darčeky pamätať vo fronte2, do ktorej ich najprv dáme. Kúpiteľné si potom môžeme pamätať v zásobníku3. Potom, keď budeme presúvať nejaký darček D z nekúpiteľných do kúpiteľných, tak vieme, že D bol najlacnejší z nekúpiteľných a bude najdrahší z kúpiteľných.

Nakoľko každé presunutie robíme v konštantnom čase a každý darček presunieme maximálne raz, dostávame riešenie s časovou zložitosťou \(O(m+n)\) a potrebnou pamäťou \(O(n)\).

Všetky spomenuté dátové štruktúry sa dajú pekne implementovať pomocou poľa.

#include <cstdio>

int darceky [1000001];                 //vsetky darceky

int main () {
  int n, m;
  scanf("%d %d ", &n, &m);
  for(int i = 0; i < n; i++){
    scanf("%d ",&darceky[i]);
  darceky[n] = 1000000001;             // na koniec pridame zarazku (velky darcek, ktory si nikto nemoze dovolit)
  int zasobnik[n];                     // zasobnik na darceky
  int v_zasobniku = 0;
  int spracovanych_darcekov = 0;
  bool je_prve = true;
  
  for(int i = 0; i < m; i++){
    int clovek;
    scanf("%d ", &clovek);
    while(darceky[spracovanych_darcekov] <= clovek){ // pridame do zasobnika vsetky potencialne kupitelne darceky
      zasobnik[v_zasobniku] = darceky[spracovanych_darcekov];
      v_zasobniku++;
      spracovanych_darcekov++;
    }
    
    if(!je_prve)
      printf(" ");
    je_prve = false;
    if(v_zasobniku > 0){               //predame najdrahsi darcek
      v_zasobniku--;
      printf("%d", zasobnik[v_zasobniku]);
    }
    else{
      printf("0");
    }
  }
  printf("\n");
  
  return 0;
}

Prípadne vieme použiť aj knižničné funkcie a štruktúry ako queue (fronta) a stack (zásobník).

#include <cstdio>
#include <stack>
#include <queue>

using namespace std;

int main () {
  int n, m;
  stack<int> kupitelne;
  queue<int> nekupitelne;

  scanf("%d %d ", &n, &m);
  int pom;
  for(int i = 0; i < n; i++){
    scanf("%d ", &pom);
    nekupitelne.push(pom);
  }
  nekupitelne.push(1000000001);        // pridame si na koniec zarazku (velky darcek, ktory si nikto nemoze dovolit)
  
  bool je_prve = true;
  for(int i=0; i<m; i++){
    int clovek;
    scanf("%d ",&clovek);
    while(nekupitelne.front() <= clovek){
      kupitelne.push(nekupitelne.front());
      nekupitelne.pop();
    }
    
    if(!je_prve){
      printf(" ");
    }
    je_prve = false;
    
    if(!kupitelne.empty()){            //predame najdrahsi darcek
      printf("%d", kupitelne.top());
      kupitelne.pop();
    }
    else{
      printf("0");
    }
  }
  printf("\n");
  
  return 0;
}

  1. Standard library: http://www.cplusplus.com/reference/stl/

  2. Jednoduchá dátová štruktúra – zoznam, do ktorého na jednom konci vkladáme prvky a na druhej strane ich vyberáme.

  3. Zoznam, do ktorého vkladáme a z ktorého vyberáme na rovnakom konci

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.