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
redigeraDetta 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:
- Läs in antalet kunder, antalet kassor, och vilken tid varje kund behöver
- Anropa en funktion som fyller de tomma kassorna med personer ur kön
- Alla kassor blir betjänade en minut#Räkna antalet minuter som passerat
- Gå till steg 2 igen tills det är vår tur att betjänas
- 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; }