Tävlingsprogrammering/Uppgifter/Biblioteket

Biblioteket

Du jobbar på ett bibliotek och vill ställa tillbaka ett antal böcker i hyllorna. Hyllorna är placerade längs x-axeln. Givet i vilken hylla varje bok ska stå (en x-koordinat mellan -1000 och 1000) och det maximala antalet böcker som du kan bära samtidigt, bestäm den kortaste sträckan du måste gå för att ställa tillbaka alla böcker. Böckerna som ska ställas tillbaka befinner sig ursprungligen på position 0. Du behöver inte gå tillbaka efter att ha återställt den sista boken.

Indata

På första raden står två heltal: antalet böcker som ska ställas tillbaka N, där 1 ≤ N ≤ 100, och antalet böcker du kan bära samtidigt K, där 1 ≤ K ≤ 100. Sedan följer N rader med ett heltal på varje rad, x-koordinaten för den hylla där varje bok ska stå.

Utdata

Programmet ska skriva ut en rad med ett heltal: den minimala sträckan du måste gå för att sätta tillbaka alla böckerna.

Exempel: Indata

4 2
3
1
4
-4

Exempel: Utdata

14

Exempel: Förklaring

Du kan exempelvis börja med att ta med dig böckerna som ska till hylla 3 och 4. Därefter hämtar du boken som ska till hylla 1 och slutligen tar du boken som ska till hylla -4.

Lösning

Det första man kan notera att det går bra att först hantera samtliga böcker på ena sidan om x=0, när man är klar med dessa hanterar man den andra sidan. Vilken sida man ska ta först beror på var den bok som står längst bort står. Eftersom man inte behöver gå tillbaka efter den sista boken är det klokt att sluta med den bok som står längst bort. För enkelhetens skull räknar vi först med att man ändå måste gå tillbaka till ursprungspositionen efter den sista boken. Denna enkelsträcka kan man helt enkelt räkna bort precis innan utskriften av svaret.

När man tar ska ta alla böcker på en sida om x=0 plockar man helt enkelt på sig så många som möjligt och ställer tillbaka en efter en, sedan hämtar man så många nya som möjligt igen, men för att man ska gå så kort sträcka som möjligt måste man i första hand ta de längst bort. Antag att man har fyra böcker att placera ut, på position 1, 2, 3, 4, och att man kan ta tre böcker samtidigt. Då är det smartast att först ta böckerna 2-4 och sedan bok 1. Då måste man gå 4*2+1*2 steg = 10 steg. Om man istället skulle ta böckerna 1-3 först och sedan bok 4 måste man gå 3*2+4*2 = 14 steg istället. Man måste alltså se till att den gången man bär de böckerna som är "kvar" när man annars har haft fullastat ska vara de närmaste (mot x=0).

Pseudokod:

Läs in alla böcker, alla med negativa koordinater i en lista, de positiva i en annan
var max := så många böcker man kan ta samtidigt
var steg := 0, totalt antal steg, det vi sedan ska skriva ut
Sortera de båda listorna så att de närmast x=0 hamnar först
För var och en av listorna
 För varje bok, börja sist i listan, men stega max steg bakåt, dvs. hoppa över max-1 böcker
  steg += bok*2, (man måste ju gå tillbaka också)
steg -= |boken som står längst bort|
Skriv ut steg

#include <iostream>
#include <algorithm>
using namespace std;
 
int main(){
	int antal, max;
	cin >> antal >> max;
 
	int positiva[101], negativa[101];
	positiva[0] = 0;
	negativa[0] = 0;
	int positiva_len=1, negativa_len=1;
	int steg=0;
	for(int i=0; i<antal; i++){
		int tmp;
		cin >> tmp;
		if (tmp > 0){
			positiva[positiva_len++] = tmp;
		} else if (tmp < 0){
			negativa[negativa_len++] = -tmp;
		}
	}
	sort(positiva, positiva+positiva_len);
	sort(negativa, negativa+negativa_len);
 
	for(int i=positiva_len-1; i>=0; i-=max){
		steg += positiva[i]*2;
	}
	for(int i=negativa_len-1; i>=0; i-=max){
		steg += negativa[i]*2;
	}
	steg -= (positiva[positiva_len-1] < negativa[negativa_len-1] ? negativa[negativa_len-1] : positiva[positiva_len-1]);
	cout << steg << endl;
	return 0;
}