Tävlingsprogrammering/Uppgifter/Kölappar

Kölappar - Uppgift 2 - Onlinekvalet till PO 2007

Du råkar gå till banken i rusningstid. Ett vanligt kölapps-system används, men n kunder har lägre könummer än du. Dock är m kassor öppna. Skriv ett program som, givet hur lång tid varje kunds ärende tar, beräknar hur lång tid det tar innan det är din tur.

Varje kund har ett bankärende som tar ett helt antal minuter. Så fort det finns en ledig kassa kallas nästa person i kön fram. Kundbytet tar inget tid i anspråk. För enkelhets skull förutsätter vi att i det ögonblicket du tar din kölapp, låt oss kalla det tiden 0, så är alla kassorna lediga och m kunder kallas alltså fram omedelbart (vilket kan inkludera dig om n < m).

Indata

På första raden står två heltal: antalet personer före dig i kön (1 ≤ n ≤ 100) och antalet öppna kassor (1 ≤ m ≤ 10). Därefter följer en rad med n heltal i intervallet 1..20, antalet minuter för varje kunds ärende. Det första talet anger tiden för den första kunden i kön, det andra för den näst första kunden o.s.v.

Utdata

Programmet ska skriva ut efter hur många minuter du kallas fram och får påbörja ditt ärende.

Exempel: Indata

7 3

2 5 6 2 4 5 3

Exempel: Utdata

8

Lösning

Detta problem kan lösas som en vanlig simuleringsuppgift. Vi simulerar hur kassorna betjänar kunderna minut för minut och tar fram nästa person ur kön när en kassa blivit ledig. Blir sista personen betjänad, det vill säga oss själva, är simuleringen klar.

Man skulle kunna optimera programmet genom att hoppa fram det antal minuter som krävs tills första nästa kund har blivit betjänad istället för att ticka fram minut för minut, men detta är inte alls nödvändigt för att lösa denna uppgift.

Exempellösningen fungerar så här:

1. Läs in antalet kunder, antalet kassor, och vilken tid varje kund behöver
2. Anropa en funktion som fyller de tomma kassorna med personer ur kön
3. Alla kassor blir betjänade en minut#Räkna antalet minuter som passerat
4. Gå till steg 2 igen tills det är vår tur att betjänas
5. Skriv ut antalet minuter som krävdes

Exempellösning i C++:

//Onlinekvalet till PO 2007
//Uppgift 2 - Kölappar

#include <iostream>
using namespace std;

int nPayBoxes, nCustomers;                        //antalet kassor och antalet kunder
int cCustomer;                                    //kund på tur att bli betjänad
int customerTime[100];                            //tid som varje kund i kön förbrukar
int timeLeft[10];                                 //tid som krävs för kunden i kassan att bli kvar

//###### Fyller tomma kassor. Returnerar sant ifall det är vår tur att bli betjänad ######
bool fillPayBoxes(void){
  for(int i = 0; i <= nPayBoxes - 1; i++){        //loopar igenom kassorna
    if(timeLeft[i] == 0){                         //kassa nr i är ledig...
      if(cCustomer == nCustomers){                //...det är vår tur att bli betjänad...
        return true;                              //...avbryt simuleringen!
      }else{                                      //det är någon framför oss i kön...
        timeLeft[i] = customerTime[cCustomer];    //...betjäna denna person
        cCustomer++;                              //...kön går ett steg framåt
      }
    }
  }

  return false;                                   //vi blev inte betjänade detta steget
}
//################ Slut på fillPayBoxes  ################################

int main(void){
  int i;
  int nMinuter;                                         //tid som krävs tills vi når kassan

  //-------------- läs in datan ---------------------
  cin >> nCustomers >> nPayBoxes;                       //läs in antalet kunder och antalet kassor	
  for(i = 0; i <= nCustomers - 1; i++){
    cin >> customerTime[i];                             //läs in vilken tid kund nr i behöver
  }
  //------------------------------------------------------------

  for(i = 0; i <= 9; i++) timeLeft[i] = 0;              //alla kassor är tomma i starten
  cCustomer = 0;                                        //ingen kund betjänad än

  //------ loopa systemet tills det är vår tur ------
  nMinuter = 0;                                         //startvärde för tiden är noll
  while(fillPayBoxes() == false){                       //fyll eventuella tomma kassor tills det är vår tur
    nMinuter++;                                         //räkna hur många minuter som passerat
    for(i = 0; i <= nPayBoxes - 1; i++) timeLeft[i]--;  //alla kassor har blivit betjänade en minut
  }
  //---------------------------------------------------------------

  cout << nMinuter << "\n";                             //printa tiden som krävdes

  return 0;
}

En lösning som använder standardbiblioteket.

#include <iostream>
#include <vector>
int main()
{
// Antalet minuter sätts till -1 för att då kunderna går till kassorna räknas som en gång
       int x, cur=0, min=-1; 
       std::cin >> x;
       std::vector<int> kund(x);
       std::cin >> x;
       std::vector<int> kassa(x,0);
       std::vector<int>::iterator itr;
       for(itr = kund.begin(); itr != kund.end(); ++itr)
       {
               std::cin >> x;
               *itr = x;
       }
 // Då cur överstiger kund.size() slutar iterationen. Detta för att cur benämner antalet 
// kunder som HAR varit vid kassan. Då antalet som har varit i kassan överstiger antalet kunder före   
/ dig så är du eller så har du varit vid kassan 
       while(cur <= kund.size())
       {
               ++min;
 // Den här iterationen är för antalet kassor som finns. För att inte låta en kund som inte             
// existerar gå fram till kassan avbryts den även om antalet kunder som har varit vid kassan 
// överstiger antalet kunder som finns utöver dig.
               for(itr = kassa.begin(); (itr != kassa.end()) && (cur <= kund.size()); ++itr)
               {
                       if (*itr >= 1)
                               --(*itr);
                       if (*itr == 0)
                       {
                               *itr = kund[cur];	
                               ++cur;
                       }
               }
       }
       std::cout << min;
}