3. Zárobkom do nového roka vzorové riešenie

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

1 0 2 2 5 2 10 20 7 0

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 STL¹ 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 fronte², do ktorej ich najprv dáme. Kúpiteľné si potom môžeme pamätať v zásobníku³. 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;
}