Tävlingsprogrammering/Uppgifter/Kötid

Uppgift

https://po.scrool.se/problems/kotid

Lösning

Delpoäng

För att få delpoäng på det här problemet så räcker den uppenbara lösningen - vi går igenom kön för varje grupp vi avverkar och väljer den första som har storlek mindre än eller lika med nuvarande antal platser kvar i vagnen.

Full poäng

Att få full poäng på det här problemet kräver lite kunskap och erfarenhet kring datastrukturer, i synnerhet binära sökträd.

Det kluriga med den här uppgiften är att komma på hur man för något värde X hittar det första värde i en sekvens (i det här fallet kön med grupper) som är mindre än eller lika med ett visst värde K (antalet platser kvar i vagnen).

Svaret är att använda sig av ett binärt sökträd. Innan några personer lastats på vagnen - låt grupperna av personer representeras av löven i ett binärt sökträd. Låt även föräldern till två noder lagra minimum av dess två barn-noders värden. Nu har vi datastrukturen vi behöver, låt oss gå igenom hur vi väljer ut en viss grupp. Anta att ett antal grupper har lastats på vagnen, och trädet har uppdaterats (vilket vi berättar hur man gör snart).

När vi vill hitta första gruppstorleken X som är mindre än ett visst K så tittar vi först på rot-nodens två barn. Anta att vänstra barnet innehåller värdet L och det högra värdet innehåller R. Om L <= K så går vi vidare till den vänstra noden. Annars går vi till den högra. Sen upprepar vi denna procedur tills vi nått ett löv - och då har vi hittat det värde vi letade efter - i logaritmisk tid.

Vi måste även hålla trädet uppdaterat när grupper tas bort allt eftersom de lastats på vagnen. Ett enkelt sätt att göra det på är att sätta det utvalda lövets värde till ett orimligt stort tal (exempelvis oändligheten), och sedan bara gå baklänges upp i trädet och återigen sätta en inre nods värde till minimum av dess två barn, ända upp till rot-noden.

Man kan även vända på problemet och för varje grupp söka efter en passande vagnstorlek, och använda max istället för min i de interna noderna. Se kod nedan.

Elegant lösning i C++ av Johan Sannemo:

#include <cstdio>
 
#define max(a, b) (a > b ? a : b);
int n, on = 1, k, seg[1<<21], p;
 
int main(){
    scanf("%d%d", &n, &k);
    while(2*n > on) on *= 2;
    for(int i = 1; i<on; i++) seg[i] = k;
    for(int i = 0; i<n; i++){
        scanf("%d", &p);
        int at = 1;
        while(at < on/2){
          if(seg[at<<1] >= p) at = at<<1;
          else at = (at<<1)+1;
        }
        printf("%d ", at - on/2);
        seg[at] -= p;
        while(at){
          at /= 2;
          seg[at] = max(seg[at<<1], seg[(at<<1)+1]);
        }
    }
}